FraPPE: Fast and Efficient Preference-Based Pure Exploration
Authors: Udvas Das
Apurv Shukla
Debabrota Basu
Venue: NeurIPS 2025 poster ()
Keywords: Bandits
Pareto Set Identification
Pure Exploration
Fixed Confidence
Sample Complexity
Preference Cone
Primary area: theory
TL;DR: A computationally efficient algorithm for identifying the exact Pareto optimal set with fixed confidence and any preference cone in a vector-valued Bandit. FraPPE is provably asymptotically optimal and numerically achieves the least sample complexity

Abstract: Preference-based Pure Exploration (PrePEx) aims to identify with a given confidence level the set of Pareto optimal arms in a vector-valued (aka multi-objective) bandit, where the reward vectors are ordered via a (given) preference cone $\mathcal C$. Though PrePEx and its variants are well-studied, there does not exist a *computationally efficient* algorithm that can *optimally* track the existing lower bound (Shukla and Basu, 2024) for arbitrary preference cones. We successfully fill this gap by efficiently solving the minimisation and maximisation problems in the lower bound. First, we derive three structural properties of the lower bound that yield a computationally tractable reduction of the minimisation problem. Then, we deploy a Frank-Wolfe optimiser to accelerate the maximisation problem in the lower bound. Together, these techniques solve the maxmin optimisation problem in $\mathcal O(KL^{2})$ time for a bandit instance with $K$ arms and $L$ dimensional reward, which is a significant acceleration over the literature. We further prove that our proposed PrePEx algorithm, **FraPPE**, asymptotically achieves the optimal sample complexity. Finally, we perform numerical experiments across synthetic and real datasets demonstrating that **FraPPE** achieves the lowest sample complexities to identify the exact Pareto set among the existing algorithms.

FraPPE: Fast and Efficient Preference-based Pure Exploration
Udvas Das Univ. Lille, Inria CNRS, Centrale Lille UMR 9189 CRISIAL, Lille, France
Apurv Shukla
Department of EECS, University of Michigan Ann Arbor, MI, USA apurv. www.ssshulluuiic.ccomm edu
udvas das@inria.fr
Debabrota Basu
Univ. Lille, Inria CNRS, Centrale Lille
UMR 9189 CRIStAL, Lille, France debabrota. basu@inria.fr
Abstract
Preference-basee Pure Exploration (PrePEx) aims identify with a given confi- dence level the set of Pareto optimal arms in vector-valued (aka multi-objective) bandit, where the reward vectors are ordered via a (given) preference cone C. Though PrePEx and its variants are well-studied, there does not exist computa- tionally efficient algorithm that can optimally track the existing lower bound (Shukla and Basu, 2024) for arbitrary preference cones. We successfully fill this gap by efficiently solving the minimisation and maximisation problems in the lower bound. First, we derive three structural properties of the lower bound that yield com- putationally tractable reduction of the minimisation problem. Then, we deploy a Frank-Wolfe optimiser to accelerate the maximisation problem in the lower bound. Together, these techniques solve the maxmin optimisation problem in OKL time for bandit instance with K arms and L dimensional reward, which is significant acceleration over the literature. We further prove that our proposed PrePEx algorithm, FraPPE, asymptotically achieves the optimal sample complex- ity. Finally, we perform numerical experiments across synthetic and real datasets demonstrating that FraPPE achieves the lowest sample complexities identify the exact Pareto set among the existing algorithms.
Introduction
Randomised experiments are at the core of statistically sound evaluation and selection of public policies (Banerjee et al., 2020), clinical trials (Altman and Dore, 1990), material discovery (Raccuglia et al., 2016), and advertising strategies (Kohavi and Longbotham, 2015). They allocate set of participants to different available choices, observe corresponding outcomes, and choose the optimal with statistical significance. As these static and randomised experimental designs demand high number of samples, has invoked a rich line of research in adaptive experiment design (Hu and Rosenberger, 2006; Foster et al., 2021), 1), also known active (sequential) testing (Yu et al., 2006; Naghshvar and Javidi, 2013; Kossen et al., 2021) or pure exploration problem (Even-Dar et al., 2006; Bubeck et al., 2009; Carlsson al., 2024). Pure exploration problems sequentially allocate participants to different available choices while looking into past allocations and outcomes. The aim to leverage the previous information gain and structure of the experiments and observations to identify the optimal choice with as few number of interactions as possible. Even in this age of data,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

pure exploration draws significant attention in diverse settings, such as material design (Gopakumar et al., 2018), clinical trials (Villar al., 2018), medical treatments (Murphy, 2005). where each observation involves a human participant or is costly due to the involved experimental infrastructure.
In this paper, we focus on multi-armed bandit formulation of pure exploration (Thompson, 1933; Lattimore and Szepesvári, 2020), which is a theoretically-sound and popular framework for sequential decision-making under uncertainty, and the archetypal setup of Reinforcement Learning (RL) (Sutton et al., 1998). In bandits, a learner encounters an instance of K decisions (or arms). At each time step t, a learner chooses one of these K-arms At, and obtains a noisy feedback R. (or reward or outcome) from the reward distribution corresponding to that arm, i.e. VA,, Note that each reward distribution has a fixed mean Ma which is unknown to the learner. The goal of the learner is to adaptively select the arms in order to identify the arm with the highest mean reward with a statistical confidence level and the least number of interactions. This popularly known as the fixed-confidence Best Arm Identification (BAT) problem (Jamieson and Nowak, 2014; Garivier and Kaufmann, 2016; Soare et al., 2014; Degenne et al., 2020; Wang et al., 2021), which is special case of pure exploration.
PrePEx: Motivation. The classical BAI and pure exploration literature, like most of the traditional RL literature, focuses on scalar reward, i.e. single or scalarised objective. But this does not reflect the reality as often decisions have multiple and often conflicting outcomes (Gopakumar et al., 2018; Wei al., 2023), and we might need to consider all of them before selecting the 'optimal' one. For example, in clinical trial, the goal is not only to choose the most effective dosage of drug but also to ensure it is below a certain toxicity level (Réda et al., 2020). Another example is phase II vaccine clinical trial, known as COV-BOOST (Munro et al., 2021), that measures the immunogenicity indicators (e.g. cellular response, anti-spike IgG and NT50) of different Covid-19 19 vaccines while applied as a booster (third dose). It is hard for a computer scientist to design a scalarised reward out of these indicators (known as the reward design problem), and different experts might have different preferences over them. Even in high-data regimes, proper reward modelling has emerged as a hard problem in Reinforcement Learning under Human Feedback (RLHF) literature (Scheid et al., 2024).
These evidences motivates us to study a multi objective (aka vector valued) bandit problem, where the reward feedback at every step is an L-dimensional vector corresponding to L-objectives of the learner. Additionally, the learner has access to set of incomplete preferences over these objectives that together form a preference cone C (Jahn et al., 2009; Löhne, 2011) 1). For example, polyhedral cones, positive orthant cone (T.4). and customised asymmetric cones are used in aircraft design optimisation (Mavrotas, 2009). portfolio optimization balancing return, risk, and liquidity (Ehrgott, 2005), and climate policy optimization with multiple national goals (Keeney and Raiffa, 1993), respectively. In these cases, there might not exist an optimal arm but a set of Pareto optimal arms P' (l. KJ (Drugan and Nowe, 2013; Auer et al., 2016).
Given the preference cone C and sampling access to the bandit instance, the learner aims to exactly identify the whole Pareto optimal set of arms with a confidence level at least 1 1-6 å E [0. 1) while hoping to use as less samples as possible. This problem known as the Preference-based Pure Exploration (PrePEx) (Shukla and Basu, 2024), or Pareto set identification (Auer et al., 2016) or vector optimisation with bandit feedback (Ararat and Tekin, 2023).
PrePEx: Related Works. There are mainly three types of algorithms proposed for PrePEx: suc- cessive arm elimination, lower bound tracking, and posterior sampling-based. Successive arm elimination algorithms use allocations to collect samples from arms and eliminate them one by one when enough evidence regarding their suboptimality is gathered (Auer et al., 2016; Ararat and Tekin, 2023; Korkmaz et al., 2023; Karagözlü et al.. 2024). But all of them can identify only an approximation of the Pareto optimal set. The same limitation applies for confidence bound based algorithms (Kone et al., 2023a). In contrast, the lower bound tracking algorithms first derive a lower bound on the number of samples required to solve PrePEx as a max-min optimisation problem. Then following the Track-and-Stop framework (Kaufmann et al., 2016), at every step, these algorithms plug in the empirical estimates of means of the objectives (obtained via previous samples) in the lower bound optimisation problem and obtains candidate allocation policy. The allocation leads to a choice of the arm at every step till the algorithm confident enough to identify the correct set of arms. But this optimisation problem is challenging, and only recently, Shukla and Basu (2024) proposed an explicit lower bound for any arbitrary preference cone. Since their lower bound contains optimisation over non-convex set, they construct convex hull of the non-convex variables and use it to propose a sacck-and- Stop algorithm, PreTS. But it is computationally infeasible to run PreTS for
2

---

Methods
Computational Complexity'
Preference Cone
Beyond Gaussian
Crepon et al. (2024)
O (33+
Positive orthant
X
Kone et al. (2024)
O (K2L min K, LJ)
Positive orthant
X
Shukla and Basu (2024)
Intractable
Arbitrary cone
FraPPE (This paper)
O (K L, L))
Arbitrary cone
Table I: Comparison of asymptotically optimal algorithms for solving PrePEx
the benchmarks in the literature. Crepon et al. (2024) focuses only on the right-orthant as the cone and propose a specific optimization method by adding and removing points from the Pareto set. Still, is computationally inefficient (O(K²) runtime) to run it on existing benchmarks (Kone al., 2024). The complexity of this optimisation problem has motivated Kone et al. (2024) to avoid it and propose a posterior sampling-bast based algorithm. Further discussion on related works is in Appendix A.
Contributions. We affirmatively address (Table 1) an extension of the open problem (Crepon et al., 2024): Can design computationally efficient (polynomial in both K and L.) and statistically optimal PrePEx algorithms beyond Gaussian rewards and independent objectives, and for arbitrary preference cones?
(I) Tractable Optimisation: We leverage the structure of the PrePEx problem to reduce the in- tractable sup- inf - inf - inf optimisation problem in the existing lower bound to a tractable max min min min problem. This shows the redundancy of the convex hull approach of PreTS and solve the inner minimisation problems in O L min ( K, -}} time. In practice, K > L, and thus, this is a significant improvement over the existing optimisation baasdsd (Crepon et al., 2024) algorithms exhibiting ((K²) computational complexity. (2) Asymptotically Optimal and Efficient Algorithm: We further leverage the Frank-Wole algorithm (Wang et al., 2021) to solve the outer maximisation problem for exponential family distributions and relaxed stopping criterion propose FraPPE. We prove a non-asymptotic sample complexity upper bound for FraPPE and shows it to be asymptotically optimal as 5 + O. (3) Empirical Performance Gain: We conduct numerical experiments across synthetic datasets with varying correlations between objectives and a real-life dataset (COV-BOOST). The results show that FraPPE enjoys the lowest empirical stopping time (~5-66 6X lower) and the lowest empirical error uniformly over time among all the baselines.
In brief, we propose the first computationally efficient and asymptotically optimal algorithm, FraPPE. that works for arbitrary preference cones and exponential family distributions while achieving the lowest sample complexity and probability of error for identifying the exact set of Pareto optimal arms.
2 Problem Formulation: Preference-based Pure Exploration (PrePEx)
First, we formally state the preference based pure exploration problem under the fixed-confidence setting and elaborate the relevant notations.
For any n N, [n]] denotes the set {1,2,.... n.). Ze refers to the 4 component of a vector z. We use || Ip to denote the norm of vector. (ec is the vectorized version of matrix A. AK represents the simplex on [K] and DKL (P) Q) refers to the KL-divergence between two absolutely continuous distributions P and Q. ch [X} means convex hull of a set X.
Notations.
Problem Formulation. In PrePEx, we deal with a multi-objective bandit problem. A bandit environment consists of K arms and each arm yields L-dimensional reward corresponding to the L objectives. Specifically, each arm a E [K] has a reward distribution V4 over R. with unknown mean M, 1R4, Thus, a bandit environment is represented by the vectors of mean rewards {u:) or alternatively, matrix M E R such that its th column is pt..
At each time N. the learner pulls vector R. sampled from VA,- In the simplest setting of pure exploration, i.e. Best Arm Identification (BAI), we have L and the leameer focuses finding the best arm, i.e. the arm with highest mean (Garivier and Kaufmann, 2016). In more general settings with L = 1, the learner aims to find a policy ग E AK indicating the proportion to choose the arms to maximize the expected reward obtained from the environment (Carlsson et al., 2024).
A, E [K] and observes T-dimensional reward
We ommit the complexity of calculating Pareto set. i.e. OKK K) m))xx(L,L-2)) as it is same for every method (Kung et al., 1975).
3

---

Pareto Optimality and Preference Cones. Since we have mean vectors (L > 1), we need set of preferences over the objectives to compare the means rewards of arms or policies. Thus, following the vector optimization literature (Jahn et al., 2009; Löhne, 2011; Ararat and Tekin, 2023), we assume that the learner has access to an ordering cone C.
Definition (Ordering Cone). A set C S RR is a cone if E C implies that ov E C for all a 2 0. solid cone has a non-empty interior, i.e. iC) + 0. A pointed cone contains the origin. A closed convex cone that is both pointed and solid called an ordering cone (aka a proper cone).
Following PrePEx literature (Ararat and Tekin, 2023; Karagözlü al., 2024; Shukla and Basu, 2024), we focus on the polyhedral ordering cone that induces a set of partial orders on vectors in IR..
Definition 2 (Polyhedral Ordering Cone). A cone C is polyhedral ordering cone if - {o R4 | 2 0}, where W E R x with row-transposes W.T representing rays spanning the cone.
W called the half-space representation of C. An example of polyhedral cone is CT/4 {(r cos 0, sin 0) E IR2 r 2 0 E //4), i.e., all the 2-dimensional vectors that makes an angle less than x //4 with the ær-axis. The commonly used cone in the Pareto set identification literature (Kone et al., 2023a,b; Crepon et al., 2024) is the positive orthant R4, i.e. Ca/2-
To avoid any redundancy (Ararat and Tekin, 2023; Shukla and Basu, 2024), we assume that W is full row-rank and normalized, i.e. [|&ll2 1. Hereafter, we call them preference cones, and the vectors in the cone as the preferences. For simplicity, in this paper, we consider that the preferences are normalised, i.e. z E CC C. We now define the partial orders w.r.t. a preference cone C.
Definition 3 (Partial Order). For every μe v¹ E IR_, j S Jt' if ja E p + E and μ -e Jl' if I E μx' + int(C). Alternatively, μa Ie pt is equivalent to z (μ 1x) S O, Vz E C+. Here, C+ is the dual cone C.
The partial order induced by C induces further order over the set of arms [K]. Specifically, given any two arms i,j [K]: (i) arm weakly dominates arm iff pe; 3c p1.. (ii) arm j dominates arm i iff i4 (etto) My, (ii) arm j strongly dominates arm iff pt <C pt..
Definition 4 (Pareto Optimal Set and Policies). An arm i [K] is Pareto optimal if it is not dominated by any other arm w.r.t the cone C. The Pareto optimal set P is the set of all Pareto optimal arms. The set of Pareto optimal policies (also known as Pareto front) II? C CAx is the set of non-dominated distributions having support on subsets of Pareto optimal arms.
In Figure 1, we show the Pareto optimal arms for the SNW dataset with K 256 and et al., 2012a) For the preference cone C2/2. the blue points represent the mean rewards of the Pareto optimal arms, whereas for C22/3- the Pareto optimal arms correspond to green points (the blue and red lines show respective Pareto fronts). This shows how preference cones affect Pareto optimality.
(Zuluaga
Generally, PrePEx aims to identify all the distributions over the arms, i.e. the policies π E AR. lying on the Pareto optimal policy set. Given a preference cone C and the bandit instance M, learner can solve a vector optimization problem to exactly identify a policy on the Pareto front, i.c. a policy whose mean reward is non- dominated by any other policy w.r.t. C. Mathematically, policy π belongs to the Pareto front ITo if
SNW Data: Pareto optimal arms and Fareto Frents
34-
Cone 90"
Cone
Objective
42.
T E arg max MTT with respect to C.
(1)
-12 Objective 1
In PrePEx, we address the problem in Equation (1), when the mean matrix M unknown a priori but bounded, i.e. || E [-M Mmax] We de- note all such instances by M. Our goal to exactly identify with as few samples as possible, all the policies lying on the Pareto front using the L-- dimensional reward feedback from the arms pulled.
Figure 1: Effect of preference cones on Pareto optimal arms in SNW dataset.
Definition 5 ((1 - -corrett PrePEx). An algorithm for Preference- based Pure Exploration (PrePEx) is said to be (1 à) correct if with probability at least 1 - ô, it returns the Pareto front 1If.

---

Lower Bound. Shukla and Basu (2024) quantify the minimum number of samples that an (1 - 6)- correct PrePEx algorithm requires identify the Pareto front as an optimisation problem.
Theorem (Lower Bound (Shukla and Basu, 2024)), Given a bandit model M E M, a preference cone C. and a confidence level 8 E (0, 1), the expected stopping time of any (1 5) cooorecttt PrePEx algorithm, identify the Pareto optimal policy set is [B[Ts] 2 TM è log 2235) where the expectation is taken over the stochasticity of both the algorithm and the bandit instance. Here, TM. is called the characteristic time and is expressed as
(TM.e)
inf WEAx TEAR (MI() (E) REC
sup
inf inf Σ k=1
wh WKD (z Ms 2 (MMx)
(2)
Here, 0A (M) A UTEAR\ATT *'EI"(M,C)
M ( MMMM M (M) 3z E C+, (vect (z(T - -+-->"))7 TT)T),, voct (MT) = 03
The lower bound tests how hard it is to distinguish given instance M and another instance M M \ {M} in the direction of a preference z E C+ that makes them the most indistinguishable. M is called an alternative instance and the set of alternative instances A (M) is called the Alt-set. Specifically, Alt-set consists of all such instances in M which has at least one Pareto optimal policy different than that of M. We aim to find out the allocation w that allows us to maximise their KL-diiergeecess and render them as distinguishable as possible.
From Lower Bound to Optimal Algorithms. A common approach to design asymptotically optimal pure exploration algorithms (e.g. Track-and-Stop (Kaufmann al., 2016)) is to solve the sup inf optimisation problem (Eq. (2)) at every step with empirical estimates of the means M obtained through bandit interaction, and stop only when one is confident about correctness this context, we derive three structural observations regarding the optimisation problem and Alt-set that allows us to design the first efficient and asymptotically optimal PrePEx algorithm for generic preference cones.
3 Structural Reduction of the Optimisation Problem
We observe that the optimisation problem in the lower bound (Equation (2)) is a combination of three inf and one sup problems. It is easy to observe that since Ax and C+ are convex and compact sets. Thus, the optimisation problem reduces to
max inf (nTTEAR\EE)) inf min WEAK xt (M. MeAA(MM REC+
Σ w DEL (z (2TMa)
f x (M)
The outer maximisation problem with respect to w, called allocation, is a linear programming (LP) problem solvable by any off-the-shelf LP-solver (e.g. CPLEX (Manual, 1987). HIGHS (Huangfu and Hall, 2018)), if all the inner inf problems can be reduced to min problems. The inner minimisation problem with respect to the preference z can be solved using an off tffetff-sheef conic programming solver (e.g. CVXOPT (Vandenberghe, 2010), CLARABEL (Towsley et al., 2022)). In the following sections, further reduce the two inf problems into min problems.
3.1 Structure of the Pareto Optimal Policy Set
We first observe that the inf problem over the set of Pareto optimal policies IIo and the complementary set of any other policies Ax \ {Tī } is costly as the sets are continuous and possibly non-conven It leaves two possibilities: (a) optimising over the convex hull of IIo or (b) reducing the optimisation problem to tractable smaller set. Constructing the convex hull is computationally expensive and might lead to looser minimum. Thus, we aim to reduce the inf problem to a bell-behaved subset of IT.. First, we observe that ITP is a compact set consisting of stationary policies from A Secondly, we prove that IT is spanned by p pure policies corresponding to the p Pareto optimal arms.
Theorem 2 (Basis of IIe), Pareto optimal policy set IP is spanned by p pure policies corresponding p Pareto optimal arms, i.e. {T) 12 Here, π is the pure policy with support on only arm i.
Detailed proof is in Appendix B.1. Thus, II" has finite number of extreme points. Given II is compact and (w, π², T (M) is continuous in π². inf x enr is equal to min, = E(m;)? (Fact 7). Now, we define the notion of neighbouring pure policies.
5

---

Definition 6 (Neighbouring Pure Policies). ;; E { is a neighbouring pure policy of ' E {Ti if any mixed policy (distribution over actions) with support Supp (TT {i,i} not dominated by any other policy. Formally, nbd (m,) & { E [TR] \ { VTr E AK. Taj with Supp (Tey)) = (i.j), M Tij Pe Tiy M )
By Carathéodory's 's theorem (Leonard and Lewis, 2015), any Pareto optimal pure policy can have up min K, L} such neighbouring pure policies. For example, neighbouring pure policies of any Pareto optimal arm in Figure are the + arms connected by the Pareto front (blue line). We also observe that since SNW dataset has
objectives, each pure Pareto optimal policy (or arm) has two neighbouring pure policies (or arms). With this structure, we obtain that inf (=r; is equal to min Enbb((m;) as f(w, n²', т MM) is continuous in π and the minimum is achieved at one of the extreme points of the polyhedra. Thus, the optimisation problem in Equation (3) reduces to
K
max min n. Enbd(()) inf WEAK
min MEDA(M) REC
wk KL
(z Me z </Mx),
(4)
1=1
- (W(()
( (M) A2ECt (vect (Z(TT-- - x;i"), vect((i))) =0} while (M(M) A Un, Enba(m)) t|m 12-1
is a subset of the Alt-set (A(M) considered in Equation (2). Thus, these observations together yield significant reduction in the complexity of the inf problem over the set of Pareto optimal policies
and their neighbours to OK min K, L)) evaluation problems of fis(w)M)
Remark (Connection to Construction of Alt-set by Crepon et al. (2024)). Crepon et al. (2024) optimise the [ww, [ww,"' π. M)) by constructing a function from the Pareto set to [T.] that computes the minimum cost of adding and removing any Pareto optimal point of M. This is combinatorial mapping with O D(K4) realisations. We accelerate it significantly by leveraging the structure of 11" and evaluate O(K min(K, L}) functions of Pareto optimal points and their neighbours.
3.2 Structure of the Alternative Set
Now, the only demanding optimisation problem left is finding the infimum over the Alternative instance M in the reduced Alt-set OM(M). We observe that for each Pareto optimal pure policy ने and its neighbouring pure policy Ty. (M) & {ME E (M) : 3z E C+, (vect (z(Tr- - -=;) vect( = =0] is a convex set. Hence, the reduced Alt-set (A(M) is a union of O(K min( L}) convex sets (Ag(M))
This observation removes the need of constructing a convex hull around the original Alt-set defined by Shukla and Basu (2024), and searching for the infimum in it. This procedure prohibitively expensive. But reducing the Alt-set to union of convex sets completely eliminates this step and we can reduce the optimisation problem (Fact 8) further:
K
max min n, enbdim?) min WEAK
min M Egy (M) ZEC
DKL
Me 1 TMMM
(5)
de(mi
Since both the innermost minimisation problems are con- vex sets, the minimisation problem in the lower bound can be solved using O(K min K, L}) calls convex optimisation oracle. For well-behaved distributions, e.g. multi-variate Gaus- sians, we have closed form solutions and can avoid the min- imisation over the Alternative instances M (Appendix B.3).
č.
135.
45"
Remark 2 (Connection to Pure Exploration with Multiple Answers). The idea of constructing Alt-set as a union of convex sets was first introduced by Degenne and Koolen (2019) for pure exploration with multiple correct answers and further elaborated in (Wang al., 2021).
Figure 2: Preference & polar cones.
"SNW dataset (K = 206, L = 2) is derived from the domain of computational hardware design, specifically concerning the optimization of sorting network configurations (Zuluaga et al., 2012b).

---

3.3 Structure of the Alternative Instance and Polar Cone
Though we have a tractable max-min optimization problem at hand, the elegant structure of the preference cones allow us to reduce the computational complexity further.
Proposition (Polar Cone Representation of Alternative Instances). For all M E MM and given Tे II and z E ubd(m?)), the set of Alternative instances takes the explicit form Aig(AM {M E M \ [M} By bd(C") such that M T M + y where y are defined with the polar cone of Le. Co & {y E R. s.I. (z,y) S 0, O. E C.).
Proposition shows that though an Alternative instance is a K X L-dimensional matrix, it can be represented by an L-dimensional vector at the boundary of the polar cone. We illustrate the geometry of this transformation Alternative instances and the optimiser is not dimension-fiee free (e.g. mirror descent (Beck and Teboulle, 2003), Vaidya's 's algorithm (Vaidya, 1996)), then this transformation reduces the computational expense significantly (For most of the real data, K > L). For multivariate Gaussians with covariance matrix Σ, we derive the closed form of the polar vector corresponding to the Alternative instance (ref. Lemma 4). Please refer to Appendix B.2 for detailed proof.
Figure 2. If an off-the-shelf convex optimiser is used to minimise over
4 Algorithm Design: Frugal and Fast PrePEx with Frank-Wolf
Enabled by the structural reductions in Section 3, we are now ready to describe the FraPPE algorithm, which is the first computationally efficient, optimisation-drive algorithm for exact detection of the Pareto optimal set. We begin by stating the required assumption to build FraPPE.
Assumption 1 (L-Parameter Exponential Family). Let X = (X XL) be L-dimensional random vector with a distribution Po. 0 E θ and mean μ E .M C RR. Suppose XI...., X, are jointly continuous. Then, the family of distributions {Po. 9 )} belongs to the L parameter exponential
family if its density of X can be represented as f(X & h(X) exp (n(0)T(X)
(()).. rj :O
I= is the natural parametrization for some s 2 L. T' : R - R. is the sufficient statistic for
the natural parameter. h(X)) is the base density such that h RL + 10, 00). Finally, (0)
log (Ixx b(X) exp ((X)) is the log- nog-oormaliser log partition function. Additionally, we assume that the exponential family is non-singular, i.e. (2 2 3 for some 3 > 0 and for all f.
Note that the natural parameter can have dimension s greater than but in our case, only the L- dimensional mean is unknown. To highlight this, we call the above an L-parameter exponential family rather than s s-parameter. This is a common assumption in BAI for L (Kaufmann et al., 2016; Garivier and Kaufmann, 2016; Degenne and Koolen, 2019). Rather, the Pareto front identification literature has been limited Gaussians and extending to exponential families has been an open question (Crepon et al., 2024). The non-singular curvature is also mild assumption for keeping the problem well-defined, For example, this holds true for any Gaussian with non-singular covariance matrix (See Example 1) and Bernuulis with probability of success not equal to zero or one.
4.1 Fast Optimisation of Allocations with Frank-Wolft
The outer optimisation problem in Equation (5) is Linear Program (LP) over polyhedra with respect to w. Any PrePEx algorithm solves this LP trying to estimate allocation per step. Unlike typical LP solvers, projection -free methods, like Frank- Wolfe (FW) (Jaggi, 2013), solve this smooth convex Frank-Wolfe
program more efficiently (Chandrasekaran et al., 2012). The necessary conditions for FW to converge towards the optimal allocation w/ (M) are 1. the LP under study must be smooth, 2. the gradient and curvature of the function to be maximised should not blow up at the boundary of the polyhedra.
1. Smoothness: For fixed π. E { the function sis(w M) is smooth only at the minima πy e arg migmii Eubdd(=:)) fir(w] M). As suggested by Wang et al. (2021), we can adapt FW cope with non-smooth objective function by constructing r-sub-differential set close to the non-smooth points. We define the differrefential set
r)( & ch VWfo(((M) folw)M) < min fis()M) + Vee I1",, ny nbd (m:)) (6) x
7

---

Algorithm 1 FraPPE- Frugal and Fast Preference-Based Pure Exploration
1: Input: Confidence level å and sequence {re)e21 = -1-0.9/ /K
2: Initialise: For E [K] sample each arm once s.t. WK (1/K, -. ,,/, mean estimate M
3: while Equation (8) is FALSE do
4: if Vt/K N or Mc & MM then
5: Forced Exploration: w/ + (1/K,
6: else
7:
Calculate Pareto indices Ps based on current estimate Mr. Estimate Set of Pareto Policies: II consisting pure policies with it Pe as basis. Set of Neighbours: II II: where is the set of all pure policies.
Estimate Pareto Indices:
8:
9:
10:
Construct Sub-Differential Set: Hs, (e) using Equation (6)
11:
FW-Update: X f arg max min (x (t), Wi41 + क Xc+1 + r..
wEAR, hef st, (Weir))
12:
end if
C-tracking: Play A, arg min Na.t E W, (ties broken arbitrarily)
14:
Feedback and Parameter Update: Get feedback R2 E IR4 and update M, to Me+1 with R.
15:
end while
16:
Recommendation Rule: Recommend P, as the Pareto optimal set
As computing gradient in the neighbourhood w is expensive, FW further simplifies the outer maximisation and calculates the allocation in two simple steps by linearising follows
X arg max min (x We. h), Wit1 t+1 wi xEAx heHur(w.r)
t+1 X++1-
We further prove (Appendix D) that w + (w)(wr) r) continuous and continuously differentiable.
2. Gradient and Curvature. For FW to converge, boundedness of the gradient and curvature constant necessary. Lemma 1 ensures that the FW converges to the optimal allocation (ref. Appendix D).
Lemma 1. If Assumption holds true, then for all M E M: Bounded gradients:
W (w] D for all TT and w Ak. 2. Bounded curvature: (istt)My(AAy) S 8Da for all i,j. y (0, 1/K), and some a 0. Here, (A()) is curvature constant of concave differentiable function f in set (Defimition 8) and AKn A {w AK ming W. 2 )
Lemma allows to further accelerate the linearised optimisation in Equation (7) in O ( instead of standard FW complexity O (g) (Jaggi, 2013), where tol the tolerable error margin for the optimisation. Thus, we propose the first PrePEX algorithm for general exponential familly whereas
existing literature is restricted to Gaussian or Bernoulli (Crepon al., 2024).
4.2 FraPPE: Frugal and Fast PrePEx
We propose FraPPE for efficient (Frugal and Fast) identification of all the Pareto optimal arms in PrePEx. FraPPE follows the three component-bas based design from pure exploration literature (Kauf- mann et al., 2016; Degenne and Koolen, 2019; Wang et al., 2021).
Component 1. The first component of FraPPE is hypothesis testing scheme based on sample statistic (Line 3 in Algorithm 1) that decides whether the algorithm should stop sam- pling and recommend the estimated Pareto optimal the "Stopping Rule". We revisit the stopping rule described by Shukla and Basu (2024):
as the optimal one. This is called
min er minzec+ Ekn NI.. x (TTMa.)) TTM, 2 c(l,5). We note that construct- ing convex hull around the Alt-set per iteration is computationally expensive and not really tractable. Instead, we take advantage of Equation (5) to deploy a tractable and efficient stopping rule:
min |., EII
min (
inf (M #EC+
min Σ
k=1 NR.
(z (zTMa..
Me) 2 c(t, 6)
(8)
(m(+t
where c(t,
K k 3ln (1 + In (Na.)) + KG
For explicit expression of G(-) R
Rt refer to Theorem 13 (Kaufmann and Koolen, 2021). The intuition behind this stopping rule
8

---

stems from the Sticky Track-and-Soe strategy for multiple correct answers setting (Degenne and Koolen, 2019) that stops as soon as it can identify any one of the correct answers (Pareto arms in our case). Though in our setting, we need to rule out the possibility of choosing confusing instance for all the correct answers, i.e. the Pareto arms. Hence, we take minimum over the finite set of Pareto optimal policies {T) ) Note that, (8) is the first Chernoff-type stopping rule that encapsulates the effect of C that has been unresolved in the literature (Crepon et al., 2024).
Component 2. The next component of FraPPE is a "Sampling Rule". It chooses the action to play based on the allocation W/ estimated via Equation (7) (cf. Section 4.1). We use "C-tracking" (Line 13, Algorithm 1) as the other variant "D-tracking" fails to converge to w (M) for multiple correct answers (Degenne and Koolen, 2019). We refer to Appendix for convergence and other results.
Component 3: Once the stopping rule is fired i.e., flag is TRUE, FraPPE recommends the estimated Pareto arms as the set of correct answers. The stopping rule ensures that the Pareto arms given by "Recommendation rule" are correct with probability at least (1 - 5) (Theorem 13).
Sample Complexity. Now, we show that FraPPE is an asymptotically optimal PrePEx algorithm.
Lemma (Sample Complexity Upper Bound). For any M E M, E (0,1), and preference cone C.
expected stopping time satisfies lim [
E[T,] S TM.C--
Thus, FraPPE achieves asymptotic optimality. We also prove correctness (Theorem 6) and derive a non-asymptotic sample complexity bound (Lemma 6 in Appendix E.4), which we omit for brevity.
Computational Complexity. First, Line 7 suffers worst-case complexity for estimating Pareto set using the algorithm of Kung et al. (1975) is O (K log(K) mmxx))))), (Kone et al., 2024). Then, for each { Ji=1 and { Inbd(r))) Component 1 and Frank-Wolfe step (Line 11) enjoys time complexity O (L) due to K K-inddepeneent bound over curvature and gradients (Lemma 1 (Jaggi, 2013)).
Thus, FraPPE has the total time complexity O (max { K (log K [()max(1.L-2] K min K, )}}).
Note that, for L 2 5 and K 2 19, runtime of FraPPE is O ((log -)max(1,L-21). i.e. the Pareto set computation becomes the dominant component. We refer to Appendix G.1 for detailed discussion.
Experimental Analysis
We perform empirical evaluation of FraPPE on a real-life dataset as well as synthetic environment.
Benchmark algorithms. We compare our algorithm with PSIPS (Posterior concentration based Bayesian algorithm (Kone et al., 2024)), APE (Approximate Pareto set identification (Kone et al., 2023a)), Oracle that pulls arms according w* (Ad), i.e., the optimal allocation, Uniform sampler, and also TnS (Gradient based algorithm in (Crepon et al., 2024)). We consider c(1, 6) = In( (+))((2)
This real- inspired data set contains tabulated entries of phase-2 booster trial for Covid-19 (Munro et al., 2021). Cov-Boost has been used as a benchmark dataset for evaluating algorithms for Pareto Set Identification (PSI). It consists bandit instance with 20 vaccines, i.c. arms, and 3 immune responses as objectives, i.c., K 20 and L = 3.
Experiment 1: Cov-Boost Trial Dataset.
Observation. (a) Lower and Stable Sample Complexity. In Figure 3, we plot the stopping times for 8 0.01 that validates the frugality of FraPPE in terms of median sample complexity. Additionally, we observe very less variability compared to PSIPS which leverages posterior sampling, which makes FraPPE more stable strutegy. For 0.1, Kone et al. (2024) states that PSIPS has an average sample complexity of 20456, while TnS of Crepon et al. (2024) reports it to be 17909. FraPPE exhibits an average sample complexity of 3523 (~5-6X less) over 100 independent experiments.
(b) Low Error probability. In Figure 5, we visualise the evolution of average error 1(p, # P*) for FraPPE against PSIPS and Uniform explorer. FraPPE reduces the error rate significantly faster.
Experiment 2: Effect of Correlated Objectives. We also test FraPPE on the Gaussian instance of Kone et al. (2024) used with 5 arms, 2 objectives, and the covariance matrix with unit variances. Correlation coefficients are varied from -1 to 1 with grid size 0.1, We fix = 0.01. We compare the empirical performance with PSIPS is the only algorithm tackling correlated objectives.
Observation: Uniformly Better Performance across Correlations. We plot the average sample complexity (averaged over 1000 runs for each correlation coefficient) in Figure 4. It shows that

---

100K
Average Stopping Time
PSIPS
FraPPE
Stopping Time
80K
60K
104
40K
20K
0K
FraPPE
PSIPS
APE
Orade
Uniform
Tns
124
Correlation Coefficient
Figure 4: Effect of correlated objectives on Gaus-
Figure 3: Stopping times for Cov-Boost Trial.
sian instance.
1.0
PSIPS
Probability of Error
Uniform
FraPPE
0.6
0.4
0.2
1000
2000
3000
4000
5000
Iteration
Figure 5: Error probability evolution for Boo-Boost Trial.
FraPPE achieves better sample frugality than PSIPS across all the values of correlation coefficients. Notably, the standard deviation of FraPPE is also narrower indicating its stability across instances.
Summary. Thus, based on the results from Experiments 1 and and computational complexity guaranty, we conclude that FraPPE is the PrePEx algorithm with the lowest empirical stopping time (5X lower), better true positive rate, and lower computational complexity among the optimixation- based baselines. Further results on runtime analysis of FraPPE are provided in Appendix J.
Discussions and Future Works
We study the problem of preference based pure exploration with fixed confidence (PrePEx) that aims to identify all the Pareto optimal arms (and policies) for a multi-objective (aka vector-valued) bandit problem with an arbitrary preference cone. We study the existing lower bound for this problem and through three structural observations regarding the Pareto optimal policies, alternating instances, tractable optimisation problem. We further apply Trank-Wolfe
and the Alt-set, we reduce based optimisation method and a relaxed stopping rule to propose FraPPE. FraPPE is the first PrePEx algorithm that is asymptotically optimal, can handle generic exponential family distributions. and thus, resolving most of the open questions in (Crepon et al., 2024). Experiments show that FraPPE achieves around 5X less sample complexity to identify the exact set of Pareto optimal arms across instances.
Throughout this work, have assumed know the exact cone C. Thus, learning the simulta- neously while solving PrePEx is an interesting future direction of research. Another future work is scale FraPPE practical applications of PrePEx, e.g. aligning large language models with RL under Human Feedback (RLHF) (Ji et al., 2023). It would be also interesting to extend our algorithm design from independent arms structured bandits (c.g., linear, contextual).
Acknowledgment
DB and UD acknowledge ANR JCJC project REPUBLIC (ANR-22-CE23-0000-4 PEPR project FOUNDRY (ANR23-PEIA-000S) and Inria-ISI Kolkata associate team SeRAI. AS would like to acknowledge the suport from ONR award no. N000142412742 for funding part of this work.
10

---

References
Achiam, J., Held, D., Tamar, A., and Abbeel, P. (2017). Constrained policy optimization. In International conference machine learning, pages 22-31. PMLR.
Altman, D. G. and Dore, (1990). Randomisation and baseline comparisons in clinical trials. The Lancer, 335(8682): 149-153.
Ararat, 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
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
PMLR.
Banerjee, A. V., Chassang, S., Montero, S., and Snowberg, E. (2020). A theory of experimenters: Robustness, randomization, and balance. American Economic Review, 110(4):1206111) 1230.
Beck, A. and Teboulle, M. (2003). Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3)1677-75.
Berge, C. (1877). Topological spaces: Including a treatment of multi-valued functions, vector spaces and convexity. Oliver & Boyd.
Bubeck. S., Munos, R., and Stoltz, G. (2009). Pure exploration in multi- bandits problems. In Algorithmic Learning Theory: 20th International Conference, ALT 2009, Porto, Portugal, October 3-5, 2009, Proceedings 20, pages 23-37. Springer.
Busa-Fekete, R., Szörényi, B., and Hüllermeier, E. (2014). Pac rank elicitation through adaptive sampling of stochastic pairwise preferences. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28.
Carlsson, E., Basu, D., Johansson, F., and Dubhashi, D. (2024). Pure exploration in bandits with linear constraints. In International Conference on Artificial Intelligence and Statisties, pages 334-342. PMLR.
Chandrasckaran, V., Recht, B., Parrilo, A., and Willsky, A. S. (2012). The convex geometry of linear inverse problems. Foundations of Computationnll mathematics, 1206))805-849.
Chen, B. and Frazier, (2017). Dueling bandits with weak regret. In International Conference on Machine Learning, pages 731-739. PMLR.
Chen, L., Li, and Qiao, M. (2017). Nearly instance optimal sample complexity bounds for top-k arm selection. In Artificial Intelligence and Statistics, pages 101-110. PMLR.
Combes, R., Magureanu, S., and Proutiere, A. (2017). Minimal exploration in structured stochastic bandits.
Crepon, E., Garivier, A., and M Koolen, W. (2024). Sequential learning of the Pareto front for multi-objective bandits. In Dasgupta, S., Mandt, S., and Li, Y., editors, Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 3583-3591, PMLR
Degenne, R. and Koolen, W. M. (2019). Pure exploration with multiple correct answers. In Neural Information Processing Systems.
Degenne, R., Ménard, P., Shang, X., and Valko, M. (2020). Gamification of pure exploration for linear bandits. In International Conference on Machine Learning, pages 2432-2442. PMLR.
Drugan, M. M. and Nowe, A. (2013). Designing multi-objeccivv multi-armed bandits algorithms: A study. In The 2013 international joint conference on neural networks (IJCNN) pages 1-8, IEEE,
Ehrgott, M. (2005). Multicriteria optimization. Springer.

---

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(Jun): (070)):079-11000
Feinberg, A., Kasyanov, O., and Voomeveld,, M. (2014). Berge's maximum theorem for noncompact image sets. Journal of Mathematical Analysis and Applications, 413(2):1400-1444
Foster, A., Ivanova, D. R., Malik, I., and Rainforth, T. (2021). Deep adaptive design: Amortizing sequential bayesian experimental design. In International conference on machine learning, pages 3384-3395. PMLR.
Garivier, A. and Kaufmann, E. (2016). Optimal best arm identification with fixed confidence. In Conference Learning Theory, pages 998-1027.
Gopakumar, A. M., Balachandran, V., Xue, D., Gubernatis, J. E., and Lookman, T. (2018). Multi- objective optimization for materials discovery via adaptive design. Scientific reports, 8(1):3738.
Grinberg, R. (2017). The Real Analysis Lifesaver: all the woll you need to understand proofs. Princeton University Press.
Gu, S., Yang, L., Du, Y., Chen, G., Walter, F., Wang. J., and Knoll, A. (2024). review of safe reinforcement learning: Methods, theory and applications.
Hu, and Rosenberger, W. F. (2006). The theory of response-aue pappons-addative randomization clinical trials. John Wiley & Sons.
Huangfu, Q. and Hall, A. (2018). Parallelizing the dual revised simplex method. Mathematical Programming Computation, 10(1):119-14)
Jaggi, M. (2013), Revisiting frank-wolfe: Projection-free sparse convex optimization. In International conference on machine learning, pages 427-435. PMLR.
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, and Nowak, R. (2014). Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In 20/4 48th Annual Conference on Information Sciences and Systems (CISS), pages 1-6. IEEE.
Ji, J., Liu, M., Dai, J., Pan, X., Zhang, C., Bian, C., Chen, B., Sun, R., Wang, Y., and Yang, Y. (2023). Beavertails: Towards improved safety alignment of Ilm via a human- ceman-preference dataset. Advances in Neural Information Processing Systems, 36:24678 24704.
Jourdan, M. (2024). Solving pure exploration problems with the Top Two approach. PhD thesis, Université de Lille.
Jourdan, M., Degenne, R., Baudry, D., de Heide, R., and Kaufmann, (2022). Top algorithms revisited. Advances in Neural Information Processing Systems, 35:26791-26803.
Karagözlü, F. M., Yıldırı,, Y. C.,, Ararat, C., and Tekin, C. (2024). Learning the pareto under incomplete preferences: Pure exploration in vector bandits. In International Conference on Artificial Intelligence and Statistics, pages 3070-3078. PMLR.
Kaufmann, F., 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, and Koolen, W. M. (2021). Mixture martingales revisited with applications to sequential tests and confidence intervals. Journal of Machine Learning Research, 22(246):1-44.
Keeney, and Raiffa, H. (1993). Decisions with multiple objectives: preferences and value trade-offs. Cambridge university press.
12

---

Kohavi, R. and Longbotham, R. (2015). Online controlled experiments and a/b tests. Encyclopedia of machine learning and data mining, pages 1-11.
Kone, C., Jourdan, M., and Kaufmann, E. (2024). Pareto set identification with posterior sampling.
Kone, C., Kaufmann, E., and Richert, L. (2023a). Adaptive algorithms for relaxed pareto set identification. Advances in Neural Information Processing Systems, 36:35190-35201.
Kone, C., Kaufmann, E., and Richert, L. (2023b). Bandit pareto set identification: the fixed budget setting, arXiv preprint arXiv:2311.03992.
Korkmaz, O., Ararat, C., and Tekin, C. (2023). Bayesian vector optimization with gaussian processes.
Kossen, J., Farquhar, S., Gal, Y., and Rainforth, (2021). Active testing: Sample-efficient model evaluation. In International Conference on Machine Learning, pages 5753-5763. PMLR.
Kung, H., Luccio, F., and Preparata, F. (1975). On finding the maxima of of vectors. Journal of the ACM (JACM), 22:469-476.
Lattimore, T. and Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press.
Leonard, and Lewis, J. E. (2015). Geometry of convex sets. John Wiley Sons.
Löhne, A. (2011). Vector optimization with infinum and supremum. Springer Science & Business Media.
Manual, C. U. (1987). Ibm ilog cplex optimization studio. Version, 12(1987-2018):1.
Mavrotas, G. (2009). Effective implementation of the e-constraint method in multi-objective mathe- matical programming problems. Applied mathematics and computation, 213(2):555-465.
Munro, A. P., Janani, L., Cornelius, 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 19 vaccines as third dose (booster) following two doses chadox ncov-19 or bnt1 in the uk (cov-boost): a blinded, multicentre, randomised, controlled, phase trial. The Lancer, (113118)22288-2223
Murphy, S. A. (2005). An experimental design for the development adaptive treatment strategies. Statistics in medicine, 24( (10): 1455-1481
Naghshvar, M. and Javidi, T. (2013). Active sequential hypothesis testingl. The Annals Statistics, 21(6)22703-2738.
Raccuglia, P., Elbert, K. C., Adler, P. D., Falk, C., Wenny, M. B., Mollo, A., Zeller, M., Friedler, S. A., Schrier, J., and Norquist, A. J. (2016). Maachine-laaring-assee assisted materials discovery using failed experiments. Nature, 533(7601):73-76.
Réda, C., Kaufmann, E., and Gelahaye-Duriees A. (2020). Machine learning applications in drug development. Computational and structural biotechnology journal, 18:241-252.
Scheid, A., Boursier, E., Durmus, A., Jordan, M. I., Ménard, P., Moulines, E., and Valko, M. (2024). Optimal design for reward modeling in rlhf. arXiv preprini arXiv:2410.17055.
Shukla, A. and Basu, D. (2024). Preference-based pure exploration. In The Thirty-eighth Annual Conference on Neural Information Processing Systems.
Soare, M., Lazaric, A., and Munos, R. (2014). Best-arm identification in linear bandits. In Advances in Neural Information Processing Systems, pages 828 836.
Sutton, R. S., Barto, A. G., et al. (1998). Reinforcement learning: An introduction. MIT press Cambridge.
Szörényi, B., Busa-Fekete, R., Paul, A., and Hüllermeier, E. (2015). Online rank elicitation for plackett-luce: A dueling bandits approach. Advances in neural information processing systems, 28.
13

---

Thompson, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of samples. Biometrika, 25(3/4):285-294
Towsley, M., Stellato, B., and Boyd, S. (2022). Clarabel: A modular and efficient conic solver using operator splitting. Optimization Methods and Software.
Vaidya, P. M. (1996). A new algorithm for minimizing convex functions convex sets. Mathemat- ical programming, 73(3):291-344
Vandenherghe, 1.. (2010). The cvxopt linear and quadratic cone program solvers. Online: htp://cvxxpp. orgffdccunennaciookccommpngggg pdf. 53.
Villar, S. S., Bowden, J., and Wason, (2018). Response- adaptive designs for binary responses: how to offer patient benefit while being robust to time trends? Pharmaceutical statistics, 17(2):182-197.
Wang, P.-.., Tzeng, R.-C., and Proutiere, A. (2021), Fast pure exploration via frank-wolfe. Advances in Neural Information Processing Systems, 34:5810-5821.
Wei, W., Ma, X., and Wang. J. (2023). Fair adaptive experiments. Advances in Neural Information Processing Systems, 36:19157-19169
You, W., Qin, C., Wang, Z., and Yang. S. (2023). Information-directed selection for top-two algorithms. In The Thirty Sixth Annual Conference on Learning Theory, pages 2850-2851. PMLR.
Yu, K., Bi, J., and Tresp. V. (2006). Active learning via transductive experimental design. In Proceedings of the 23rd international conference on Machine learning. pages 1081-1088.
Zoghi, M., Karnin, Z. S., Whiteson, S., and De Rijke, M. (2015). Copeland dueling bandits. Advances in nearal information processing systems, 28.
Zuluaga, M., Milder, P., and Püschel, M. (2012a). Computer generation of streaming sorting networks.
In Proceedings of the 49th Annual Design Automation Conference, pages 1245-1253.
Zuluaga, M., Milder, P., and Püschel M. (2012b). Computer generation of streaming sorting networks. In DAC Design Automation Conference 2012, pages 1241-1249.
14

---

Appendix
Table of Contents
A Notations and Extended Related Works
16
A.1 Extended Related Works
17
B Structures Confusing Instance
B.1 Pareto Optimal Policies Pareto Optimal Arms
18
B.2 Polar Cone Characterization of Alternative Instances
18
B.3
Characterisation of Confusing Instances for Multivariate Gaussians
19
Continuity Results
21
C.I Continuity w.r.t Preferences and Alternating Instances: [u MlM) and (w)(
21
D Convergence of FW Algorithms
24
D.1 Boundedness of Gradient and Curvature of Sub-Differentials
24
D.2 Continuity the Frank- Wolfe Iterates: Sub-Differe Diff-rrefffessss
25
Final Convergence Proof
27
E Sample Complexity of FraPPE
29
E.1
Stopping Criterion
29
E.2
Almost Sure Upper Bound on Sample Complexity
29
E.3
Expected Upper Bound on Sample Complexity
30
E,4
Non-Asymptotic Sample Complexity Upper Bound Gou.............................
31
F
Concentration Result
G Algorithmic Complexity
34
G.1 Time Complexity
34
G.2 Space Complexity
34
H Tracking Results
35
Additional Experimental Details
I.1 Implementation Details
36
1.2
Pseudocode of Accelerated PreTS
37
J Runtime Analysis of FraPPE
38
K Auxiliary Definitions and Results
39
15

---

A
Notations and Extended Related Works
Notation
Description
C, <
Given convex and induced partial order C n B(1) where B(1) is an unit ball
C+
Dual cone of C
Co
Polar cone of a cone C-
K,L
Number of arms and objectives
P",
Ground truth Pareto and estimated Pareto
ME E RRXL
matrix with mean reward of arms
Allocation vector
ITP
Family of Pareto optimal policies
Pk.bk
((E) (2)
Estimated and true of mean rewards
(M)
Set of alternating instances of M for fixed मं E II? and æryndd (πT;)
ix)(X)
Interior of a set X
ch (X)
Convex Hull of set X
S
S. {M E M, 3z C: MT; 2 z MR, Vi nbd (
Confidence parameter
c(t,
Stopping threshold
(1( and (M)
Constants such that Vt > ci (M),, S log
(M
(w,
r-subdifferential set (Equation (6))
M
Confusing instance w.r.t M
tol
Error tolerance in linear optimisation
No.t
Number of pulls of arm at time N
Preference vector from the cone C
Pareto optimal policy
Neighbour of the Pareto optimal policy π
K-dimensional simplex
A K
{w Ак ming We 2 2
Preference Matrix
T6
(1 - c)-rrrettt Stopping time
y
Vector from polar cone Co
D
Upper bound on infinite norm of gradient V Vi (w M)
M
Parameter space of mean matrix
Number of Pareto optimal arms, i. cardinality the set P*
K K-dimensional vector with 1 at k-th index, and 0 elsewhere
16

---

A.1 Extended Related Works
Pure exploration in multi- bandits (MAB) has been extensively studied, particularly in the context of best-arm identification (BAI) under cinficconeeeece (Kaufmann et al., 2016; Garivier and Kaufmann, 2016) and axed-budget (Even-Dar et al., 2006) settings. In this paper we restrict ourselves to fxee-confidence setting where the goal is to recommend the arm with highest mean
reward with probability at least (1 - 8) for given confidence parameter á E (0, 1). Specially, in the last decade we have witnessed emergence of several algorithmic strategies to tackle the problem of BAT in fixed-confidence setting. To name a few, these include action elimination based approach in (Even-Dar et al., 2006; Kone et al., 2023a), LUCB strategies introduced in (Audibert and Bubeck, 2010), further in (Jamieson et al., 2014), tracking a information theoretic lower bound (Track-and- Stop) (Kaufmann et al., 2016), extended by gamification of the lower bound (Degenne et al., 2020) or acceleration by leveraging projection-fiee free convergence towards optimal allocation (Wang et al., 2021).
Pure exploration with vector feedback. Traditionally, pure exploration in BAT focuses on scalarised rewards (Carlsson et al., 2024). In contrast, we consider the problem of preference-basee pure explo- ration (PrePEx), where the agent receives vector reward upon playing an arm of dimension equal to the number of objectives (Z.) under study partially ordered by preference cone. Recently, Shukla and Basu (2024) tackle this problem by deriving a novel information-theoree sample complexity that captures the influence of the preference cone's geometry. They proposed the Preference- based Track-and-Stop (PreTS) algorithm, which leverages a convex relaxation of the lower bound and demonstrates asymptotic optimality through new concentration inequalities for vector- rewards. Kone et al. (2024), on the other hand leverages concentration on priors over reward vectors by posterior sampling to recommend the exact Pareto optimal arms. Other notable works include Auer et al. (2016), who explored Pareto Set Identification (PSI) in MABs, and Ararat and Tekin (2023), who provided gap-based sample complexity bounds under cone-based preferences. Korkmaz et al. (2023) extended these ideas to Gaussian process bandits, while Karagözlü et al. (2024) developed adaptive elimination algorithms for learning the Pareto front under incomplete preferences. Crepon et al. (2024) proposed a gradient-base -based track-and-stop strategy for exact Pareto front identification with known preference cones.
lower bound on expected
Pure exploration with multiple correct answers. We further connect the premise of PrePEx problem with the literature on pure exploration with multiple correct answers (Degenne and Koolen, 2019; Wang ct al., 2021). Unlike standard BAI, this setting assumes existence of multiple optimal answers, though proceeds to identify any one of them. The philosophy of top-K type strategies (Jourdan, 2024; Jourdan et al., 2022; Chen et al., 2017; You et al., 2023) extend this setting by efficiently identifying the top-k optimal answers. On the contrary, in PrePEx we aim to find not k, but all of the correct answers (Pareto optimal arms), being as frugal as possible.
siteerence-based bandit problems have traditionally been studied in the dueling bandit framework, that is limited to pairwise comparisons between arms (Zoghi et al., 2015; Busa- Fekete et al., 2014; Szörényi et al., 2015; Chen and Frazier, 2017). These models focus learning global ranking or identifying a Condorcet or Copeland winner based on binary preference outcomes. While such frameworks capture relative preference information effectively. they typically assume a fixed, often discrete preference structure and are studied under regret minimization. In contrast, PrePEx generalises this idea by considering vector-valued feedback and encoding preferences via convex cones, which enables us to extend towards more complex, continuous, and possibly incomplete preference structures. Unlike dueling bandits, PrePEx targets pure exploration with statistical guarantees, hoping to identify all the Pareto optimal arms with high confidence under a richer preference model.
Duelling bandits.
Connection to constrained pure exploration and safe RL. PrePEx also generalises the setting of pure exploration under known linear constraints (Carlsson al., 2024) though the notion of preference cone over objective is redundant for single objective bandit instances. In Safe RL, we consider presence of different risk constraints (c.g.. on faimess, resource allocation etc.) (Achiam et al., 2017; Gu et al., 2024). This setting resonates with PrePEx as these constraints can be modelled as conflicting objectives while performing optimisation. The preference cone in PrePEx can also encode these constraint if they are implicit (one objective must not worsen).
17

---

B Structures of Confusing Instance
In this section, will first define the Pareto policy set and prove some of its useful properties in B.1. Then, in B.2 we will introduce the novel polar cone characterisation of the alternating instances and finally in B.3 we will show the closed form of the alternating instance under multivariate Gaussian reward vectors with non-diagonal variance-covariang matrix.
B.1 Pareto Optimal Policies to Pareto Optimal Arms
Definition 7 (Pareto Policies). The set of Pareto policies is given by IIP {x: M # 3e . π V # E AK \ {T]}-
We now have some useful results regarding the set of Pareto policies.
Lemma (Compactness of Pareto Policy set). The set of Pareto policies 11" is compact set.
Proof. To prove compactness of II', we leverage Heine- Borel theorem (refer Theorem 14). It is evident that II" is an subspace of the Euclidean space RK Since complement of I1 an open set, then II is closed. It is also bounded because all clements in II" policies which consist of entries bounded in the interval [0, 1]. Thus, according to Heine-Bore theorem we can equivalently state that IT is compact, in other words every open cover of ITP has finite sub-cover.
L
Theorem 2 (Basis of HI') Pareto optimal policy set II is spanned by p pure policies corresponding to Pareto optimal arms, i.e. {T] Here, Tē is the pure policy with support on only arm
Proof. Consider the set of pure policies whose support lies on the Pareto front. For each E P define the pure policy गद E [0, 1j associated with arm as:
j=i 0, otherwise
bbbl
Further, since i E P MT Ie M 7,, V E II II', With this construction, viewing each policy vector in [0, 1]x have that the set of pure policies is linearly independent, i.e.,
c1 + c2 + + 1 = =0 = ci = = = CIP-1 0
Let ITP, \ 17 where IT is the set of pure Pareto strategies. Since is randomized policy (Lemma 3) there exists constants 2 0, ΣjPj = 1, such that π = f + P2
... PIp- p- By linearity of dot product, M π M म + P #t..... Pip M -|p---
Since each म; E ITP and P5 2 0, MT #1 P2 π2 + +... + PPp. M म.p- te M T for all
T' III III
Thus, any policy π E ITP can be expressed as linear combination of the Pareto pure strategies T. E Phhsss i Pt, Hence, proved.
B.2 Polar Cone Characterization of Alternative Instances
Proposition (Polar Cone Representation of Alternating Instances). For all M and given πH II' and π. nbd( the of alternating instances takes the explicit form Aig (M) (M M {M}- By bd(C") such that MT, -MTT + + where y are defined with the polar cone C, Le. Co (y : y R4 s.1. y) < 0, Vz ECC
Proof. Let remind the definition of the set of confusing instances
(M) A { M M {M) 3z e C+, (vect (z( m))²) vect vez)()))) 0).
which implies that M M(T, πς)-= E (C)). We characterize the polar cone, using Farkas' lemma. For C, Σ a4Wss a4 Ovi E [L], where W {w1, W2, ..., wr), ). w. 's being the basis rays of the cone C.
18

---

Using Farkas' lemma, the polar cone can be characterized as C { P p E
Ry satisfies (z, WT p) S 0, vz CJ. Therefore, by Projection Lemma, M(T, - n3) = W p bd(("). Thus, we can write
(M) M M (M) ME ee bd(C") such that Mr, - MT;; + W pj.
Defining y W p concludes the proof.
B.3 Characterisation of Confusing Instances for Multivariate Gaussians
Lemma (Confusing instances for Multivariate Gaussian rewards). Let the reward vectors follow Multi-variate Gaussian distributions with diagonal covariance matrix E with non-zero diagonal entries. Under the polar cone characterisation of the alternating instance, the polar vector has the closed form expression y = M)(i,j) - z (i,),,) y where A(i,j) - ( - π Eg & n for given o E IT? and æ E nbd (T:)). Also, AT denotes the pseudo-inverse of matrix A. The inverse characteristic time is then given by
(z MMA(i
M.C
max min WEAN Ell"
T (x;) sec+ 2E, |I (ii ( Ding(1/w<)
min
min
Proof. First, for fixed n IIo and v, E nbd (π,) we proceed by looking at the main optimisation problem under correlated Gaussian assumption,
K
min min (M) 2EC+
wk DKL
[ZMMa MR
2 2TMee
1=1
K
(z T M₁ - T Mx)
min
min
Wk
Mi
(
2z Liz
where the last line holds due to the definition of Alt-set ,5 (M). Thus, we incorporate the boundary
constraint and write the Lagrangian dual with Lagrangian multiplier y > as
K
(z T Mr z M2)²
((M,n) 7) = min
Wk
+ + Ma -T
(9)
2z Ez
k=1
We differentiate (9) with respect to M2 and equate it to zero to get the minima
Mr. L(M, 7) =
z M₁ .z Mr
Wk
(TT TT;)
z. En
(( - T )) Σz
z My = z M2
W/
We plug back the value of 2 MM in (9) to get
TT 12,22 TZE Σz
[()) = Σ 7z Mc(] TT,),
(10)
2wok
We again differentiate (10) with respect to y and equate to zero to get closed form of 7
V v,C(7) = 0
K
π 12 Σz
My(T)
TT
Wk
km
km
Σ = z MR [
Σz
b==
K
( n, 12
Wi
19

---

We define (i; _ [ - - and Eo EzEz and lastly Diag(1/wx) as a K x K diagonal matrix
MA(i.) with k-th entry as we Then 7 Eo (ltt,))lliaattt
Thus, we finally have
z ()
A(i,))
z Mr = z Mr M
| iill (i, DiaR(1/w))
Wk
z MA(i,)
= 2 M = -MM
Aw
| 1)ll 3)
z MA(i,)
= M M
(zz 1
| (i, (1, Biag(1ww))
where Aw is a K-dimensional vectors with k-th component being AliJle and At denotes the pseudo- inverse of matrix A. Now, from the polar cone characterisation discussed in Appendix B.2 we know () y E bd())). Thus we derive the closed form of the polar cone vector as
MA(i.)) - x MA(i,,))22 y
since (Aw, (i. ( biag(1/w))) /
Therefore, we also get the closed form of the inverse characteristic time for Multivariate Gaussian rewards as well.
(z MA(i,)))
M.c max min min WEAK mं EtT RyEnhd =EC+ 2 (i.
min
() Diag(1/wa)
Note that zz a rank-1 matrix and its pseudo-inverse satisfies all four Moore-Penrose conditions. Thus the identity (zz expression of the inverse characteristic time given by
1 ||x|| zz Therefore (zz ) 1. Hence, the final
(z MA((),)) 2 wEAR Ell" n, Eubdd(();) ( zec+ 2E, || [(t, Ding(1/ww))
Tu. max min min
min
Hence, conclude the proof.
20

---

C
Continuity Results
First, we remind the lower bound on the expected sample complexity of any (1 co-rrrectt PrePEx algorithm,
Theorem (Lower Bound (Shukla and Basu, 2024)). Given a bandit model M E M, a preference cone C, and a confidence level å E 1), the expected stopping time of any (1 8)-coreect PrePEx algorithm, to identify the Pareto Optimal Set
E TM.C log
(11)
2.45
where, the expectation is taken over the stochasticity of both the algorithm and the bandit instance. Here, TMe is called the characteristic time of the PrePEx instance (M,C) and is expressed as
K
(TM,c)=
max WEAN
min ; (x) (M)
min
min REC+
Σ k=1
GUDDII (z Mx Mr).
(12)
nt EnT
(y(w(M)
F(w(M)
where for a fixed nद E II and n E nbd (T+))
Au(M) a M e M (M3 Ezec, (vect (Z(TT,-<;))) vect( = =0].
Useful Notations: For maintaining brevity, we state the useful notations related to functions under continuity analysis which are followed throughout this section and beyond.
1. First, we define the following functions. For fixed M E AM)(MM),
K
(w M)
min Σ ZEc+
wh DKL. (z
(ZTMa
Mr
2 MMa
k=1
2. Again define for fixed πं IIo and n E nbd(i).
fwl(W) & min full,, (M) MEAg((M)
3. Finally, F(w] M) & min ny [u)d(())) fig (w M)
Fact 1. Due to convexity of KL divergence with respect to z E C+ and convexity of the solid cone C++ T M) is convex in z and M, but concave with respect to (Minimum over concave functions). Fact 2. As a consequence of Fact I, F(w M), being minimum among finite concave function, is concave in w. but non-smooth function. This function is smooth only at the points where the minimum is reached for πद and J.
In C.I, we state and prove continuity results of the peeled objective functions with respect to alternating instance and the preference vector.
C.1 Continuity w.r.t. Preferences and Alternating Instances: Seg(w, M) and fiz ())(
Proposition 2. Let S, M be the set of mean matrices for which πद is the Pareto optimal policy. For given कं E IT ग. E ubd( then for all (w, M) E Ax x St.
(a) For a given M e M \ M, there exists a unique Zint E <in((C+) such that
K
Zint arg min
WKL
MM
Mr
#Eint
k=
21

---

ifz'Mp Mg # 0 and z M2 + for all & = [1, K].
(b) there exists a unique Mint such that
Miat
arg argmin (MA
Σ wk DKL Ma
(c) As fn is continuously differentiable on A x Si, the gradient is expressed as
K Σ
ViJi(W[MM)
min A M.ECC+
DKL.
MM
Mr
z Mxx
ex
km1
where, eg is K --ddimnnsionll vector with 1 in k-th index, 0 elsewhere.
Proof. Proof of Part (a). We do this proof in two parts. First we prove the existence of Zinf and then its uniqueness.
Existence. We refer Theorem 11 prove the first part. define X - AxxSS Y _ int(C $ -
int(C+) and u(w, M) A Σ wa DRL. (zTM: Me z Mr). Now + (Ax x S:) 3 int(C+ is constant correspondence (as it defined before computing and M) and u A x S,xint((*)) continuous mapping. Thus fiy f M) is continuous. Hence, 2int exists.
R
Uniqueness. Now if we can prove that the KL-divergence is strictly convex in int(C*), then Zinf unique. For strict convexity, we need to show that the second derivative (Hessian) of the KL divergence w.r.t. is positive, which can be tricky if the function has flat regions or degenerate directions (which could arise at the boundary of the polyhedral cone). Here, we leverage Lemma that shows that z M2 *f and z Mr * 0 for all = [1, K]. then KL is strictly convex on z. That means as Zint E int(C*), ). for any E [K]. Mt and Mr cannot lie in int(C.). Thus, Zint exists and it is unique. Hence, proved.
Proof of Part (b). We again leverage Theorem 11 to prove existence of unique Mint- We define A Ak x S,, Y = (M)(M), + = (M)(M) and u(ws, M) ΣK W/ DRL. 2 Mr Now t (Ak x S.) 3 (M) ) is a constant correspondence (as we already fix π. ry E (T?)) (M) does not depend πi πT)) and AK S (M)
2 Mp E TT and TR is continuous mapping. Therefore, Mir upper-hemicontimuous and Juj(w)) continuous on (M). Again, the KL-divergence follows strict convexity in (M) therefore proving uniqueness of Mint-
Proof of Part (c). We leverage Lemma 11 with the following definitions X Aij(M x A AK x S,, x" (w, & Z (Minr) and u(x",w, M) ΣK w DKt. ( Ma Zinr( (Mnt))))))))
This simply proves u(x", w, M) is continuously differentiable by the virtue of continuity of
Lemma 5. For all (w, M) E Ax x S₁. DKL (aT ATM z M) ZTM) is strictly convex on z iff z Mr + 0 and z Mr + Ovk K].
Proof. The KL-divergence has the following form
L Σ
El Me, Σ Me,
DKL (z 2 TT = Σ
2i) log
km
1=1
22

---

Partially differentiating the KL with respect to 2, we get
θDKL
MMM
z
M
1= MR
Ma. Et=r
Ma.2i Mas Et= Ma
Ma.1 log
dzi
- M1
Ei Ma.121
The components of Hessian are expressed
8 DKL
2 T
z M
H1p8
Oz,dz.
a
E'=, Ma.12
Σ -i=1 M
Ma. log
Ma.1 MK.1
Ozv
Et= Mr,121
E1= Ma
K
Σl= Mai Ma. Et=1
MR.12 - Ma. Et= Ma
Mk.
Ei=1 Ma
(Etnl M2,22)²
MA.1' Et=1
MR.12i-
Ei=, Ma.12
My.1
(E
12,22)2
K
1
MN.
Ma.MMu + MM.MEr))
Σ1= MA
El=1 1z
1-1 Ms.121
+
Ma.
EE 12.1212
1=1
(MaiMay + MM..Me.)
ML. (E M2,22)2
Σ
Ma.
EE (4.12) Me,12))
(Etz Me,zi)
Thus, the Hessian of KL is positive definite iff for any non-zero x E RRL.
x Hx
>
(x M2)
(x
Mx)(x Mr)
A (x Mani >0
2
+
Au
An
A
k=
Au (x Ma)² 2 +
Ak (x T TMa2²² 2(xx Mx)(x Ma)
Ak
Au
2
A T Mr
Ào x MM >0
V
Ave
A&
This statement is always true if A4 = El= Mx.i2i # and A = MM # 0. Hence, we conclude the proof.
23

---

D Convergence of FW Algorithms
Fact 3. Frank- Wolfe is second order method. For it to converge, must ensure the gradient of the objective with respect to w is bounded around the non-smooth points and also the curvature constant must be bounded.
In this section, we first derive upper bounds on gradient and curvature constant D.1. Then we move on the state and prove continuity properties of the sub-differential set defined in (6) in D.2. Finally, unifying continuity results from C and results derived in this section, we elaborate on the convergence of Frank-Wolfe in D.3.
D.1 Boundedness of Gradient and Curvature of Sub-Differentials
Before jumping into the proof of Lemma I, we first define the curvature constant and subset of simplex that ensures the minimum index of w does not fall on the boundary of the simplex.
Definition 8. For w, w E A (0, 1] and given the bandit instance M M. the curvature constant is expressed as,
2
(AK())
22((2x) (2) ly x, V+(x)))
a² oE v=
sup a.=EAK,
Definition 9. For any (0,1/K), we define subset of the simplex AK as
K & tw AK min wk 2 7}
With these definitions in hand, now we show that the space of fiy (i(w(M) had bounded gradient and curvature w.r.t. w.
Lemma 1. If Assumption holds true, then for all M M: Bounded gradients:
fig(Wall (l) I D for all Tद J. TT and w E Dx. 2. Bounded curvature: CfgttMun( s 8Da-1 for all i,j. (0, 1/K), and some > 0. Here, C5(A) is curvature constant of concave differentiable function f in set A (Definition and AK (w Ax min; w 2 7).
Proof. Proof of 1. We already have the expression for the gradient from Appendix C as
K DKL
[ulis(W]M) = min Σ
2
M 2 1/)
ex
M.XEC Rm
Therefore
| Wi [ld(z) M,z M)
max
DKL
(z (zTMR M2
2 (M)
kE[L,K]
We know for exponential families the KL-divergence can be expressed as the Bregman divergence generated by the Cumulant Generating function or Cramer function i.e.
(KI(ll = A(p') A(μ) A(())
where A(.) is the CGF and μ. jí' belong L-parameter exponential family according to Assumption I with natural parameter 0, 0 E int(@). DKL(Hllpr) is bounded if support of 0 and O' are same, which is true in our case.
Example N oz).
Univariate Gaussian. Let, p(x) =
N(H1 and g(z)
Any of these densities has the following canonical exponential form p(x)
exp
10 2 log(2ro7)). Therefore for p(x) the natural parameter is 0
x
Ma
u2
and for the q(x)) the natural parameter is 02
02
and also the CGF is given
207
2n
by
82 + log
A(O.)
π
40v2
2
0:2

---

for i = 1. 2. Now the KL is always finite, smooth and well-behaved as long as the natural parameters belong to the same domain.
Example 2: Bernoulli. Let p(x) Ber(p), E (0, 1). Then the canonical exponential form can be written as p(z) exp x log _ + loggl - p)) Therefore the natural parameter 0 == log - which is the log-odds and the CGF is A(0) log(1 + e²). So KL--divergence between any two Bernoulli random variable X and Y with mean parameters p1 and p2 is finite and well-behaved iff P1.22 E (0, 1).
Therefore by the virtue of Assumption 1 we claim that 3D > such that the gradient is upper bounded i.e.,
[W & D. and w E Ak.
Proof of 2. We observe from the proof of part 1, fig(w M) is D-smooth, meaning for any w, w' AKT
fig(wo M) - fis(w] M) 1S (w)](()))))) ||' wll, S D 1| - wll1
Then start with the definition of the curvature constant
(((()))(AK))
a² [f)(W|M) - fey + (w w" V (ig((WMM) MY
[ M) - (1 - a) M) + afis(WIM))
+ Wi (w) oo لل - wl11
aa || - + a ||ا w111]
4D
| Tاll
a
Now, w, w' E A Kgy constant as
w - w|11 < 2. Therefore, we have the final upper bound on the curvature
8D
Cracian I
Hence, proved.
Interestingly, Wang et (2021) considered bounded gradients and bounded curvature assumption. On the other hand, in our PrePEx we get this necessary conditions for convergence automatically leveraging Assumption 1, which arguably a very generic assumption on the parametric family of the reward vectors and standard in the literature. Additionally, leveraging Lemma 1, Wang et al. (2021) could only show that boundedness of gradient and curvature constant is restricted towards only Bernoulii and Gaussian. Instead, we claim that Lemma holds for any generic exponential family satisfying Assumption
Now we move on the proving some good properties of the subdifferential set that handles the non-smoothness of fiy(w] M).
D.2 Continuity of the Frank- Wolfe Iterates: Sub-Differentials
Let's remind the definition of r-sub-diifeerenial set.
(M, A ch { [w]u(w|M) Sez (w) < min (w( + Vnj e I1,, E ubd (Ti)) (13) mims
Corollary 1. The mapping + H (w,r) is continuous.
Proof. Let (wi, Me, 000 Inbd(F[)) for some n, E nbd (TT). We can write for any h E HM(w)r),
(w) E AK S (0,1) and HM(wer)
ch { [Wwlis(w) } )-1
25

---

0} i=l [ubd(=;)) such that h can be expressed convex combina-
sequence of faz tion of (Vwfilw ,0 [ubd(mi)) Further, leveraging continuity of fas( | M) for all
j [1,] nbd (mक)) [[(ref. Appendix C), we claim that Vwlis(We M.) E Hx,, (Wi, for some t N.
Lower Hemicontinuity of subdifferential. Lower Hemicontinuity follows from the continuity result of fij derived in Appendix C.
Upper Hemicontinuity of subdifferentials. We adapt similar proof structure as Wang et al. (2021) by adding a e-radius (Minkowski addition) to H Mr, (Wi, rt) to show it is still contained by the open set containing H (w- rM) Thus, the subdifferential set is lower and upper hemicontinuous with respect to w, i.e continuous. Hence, proved.
L
Now, we prove the convergence of the Frank-Wolf Wolfe iterates. Let us remind the Frank-Wolf steps once again for brevity,
X++1 - arg max xEAx
min (w,r)
(x we. h)
(14)
Wr+1 1 1
Wi + 1 X++1
(15)
First, we define the following maps
1. 01 (w, r, M) x) + minnel (w.r) (x - w. h).
2. d2 (w,r, M) - maxxe Φ1.
Corollary 2. Φi is continuous on DKy (0,1) x St Ak.
Proof. We again leverage Theorem with the following definitions, X & AK, x (0.1) x S x AK. Y A KRK Φ(w,r, r, M, A (w, and u(w, M,, h) (x w, h). We are concerned only about continuity of the correspondence & as u is a linear function, hence continuous. Though we have already proven continuity of & in Corollary 1, Thus, conclude the proof.
Corollary 3. Φ2 is continuous on ΑKς (0, x S..
Proof. We again apply Theorem 11 with the definitions X A AKy x (0,1) x S. W AK. (ww,, r, N, M, A Aк and u(w, r, M, h) (w,,,, M, x). As a constant corresponding, we claim continuity of d2 and conclude the proof.
Theorem 3. For any > 0, 3 a constant Eı,e > O, such that if || | M 00.00
|M
< E1,er then for all
M S
max min xEAx (w
(x - w.
min (x - w. xEAx heHar(w,r))
max
< c ((w,)) E Axr x (0,1) (16)
and
E (x - w. min (x - h)) < < x(w,r,) E AKG x (0,1) x Ax (17) he.r((
min he
Proof. Proof of claim (16). We define for w e ΔKT and r E (0. 1), (M) 4
min| { 12 (,u,r,,M M) @2(w,n, r. M) }}. St. (2)
we apply Theorem 12 with the following
definitions (X) d,(w,r,10 M) 02(w,,, M) I, we claim that (MM) is continuous
AKy x (0, (( = Aky x (0. 1) and finally
MM, r)
AKy (0, 1). So, by definition of v/ 3f1. > 0, such that (M > - for all M M
100,00 < Ei...
26

---

Hence, proved.
Proof of claim (17), This proof is analogous by leveraging Corollary
Corollary 4. For any e >> O, 3 constant Ê2, > O, such that ur|lMM M -Io.0.o < <,,00 then
M S and |[ F(w|M) < <,, Ve AKy.
Proof. We define (X) S; (Y) AxT. ((M) Ax₃ and u ((M,w) - F(w M) F(w M) J. We again leverage Theorem 12 to claim that (M) & min - F(w M- M)
is continuous on the open set S,. Also, u(M) is continuous due to continuity results in Appendix C. Then, by definition of 1, 22, > O, such that (MM > - for all jM M proved.
E2, Hence,
00,00
D.3 Final Convergence Proof
Due to virtue of Lemma and continuity of Jug in Axy (ref. C), we claim that
Fact 4. M) is L-Lipschitz on AK
Proof. This fact can be simply proved by applying min-v theorem with guarantees from Lemma 1 to get for w. w' AKT
F(w|M)
min ayennd (x))
(fay(w))M)) - D || we1xo) (w]W)) 2 min
<)Endd(=;)
min TyCund(=;)
[ig(w"(M ||l w/lx F(w D |ااا w
Hence, proved. Additionally, Lipstchitzness of F can extended from AKy to k due to continuity properties proved in Appendix C.I.
Fact 5. Let E (0, ) AKy and Ag. Under Lemma 1, we have
[i](W + (y - Vii((W]M) - - M) s 8D3
where j E nbd (i) and y w + 3(x w) for some 3 EED E0,0 2)
Proof.
Sij(w|M) by Viis(W/M) - Mo(MM 22]V// 11 w/l
8D3
where the last inequality holds due to the definition of 3, x E A Hence, proved.
We can extend Fact 5 to get similar result on F(-IM) = minjenba(a) ft M) well.
Fact 6. Letr E 10,1/K), r e (0, 1), w E AKy and E Ak. Then if 3 < min { 5) then we have
8D3
Fly M) 2 F(w MM + min (y - w, h)
heHre(..))
where y (1- 3)w + 3x
27

---

Proof. Let there are two different neighbours of ; as n and f2 E nbd (x,) such that F(w |
M) fijn (w M) figa (w M) and Fly M) fizz ly M) fig. (y M). Then
w h) Fly M) - 8D3
F(w] M)
min he
7
The last inequality holds due Fact 5. Hence, proved.
Theorem 4. Let nh & (M) M) F(w, I M). Also, let t N satisfying [V $ N, then under the good events (1) G2()) and Frank- Wolfe update step defined in Equation (14) and (15) with ira > D, we have
11-1 + Tt
16DV b
1t
Proof. Using Lemma 9 and Fact have 7
and
2/tK
Fly M) 2F M) +
max
min
(x 1. 16DDVVK
WEAK he (w,(
2F M) + -0 101,V1K
The second inequality holds due to properties of HM(wwr). Refer Appendix L.2 of Wang et al. (2021) for further details. Now subtracting F'(* (MM M) from both sides and putting B we get the desired result. Hence, proved.
Therefore, for >> 4K the optimality gap becomes very small and asymptotically it converges to zero.
Theorem Let (re]121 be a sequence of positive numbers with the properties lim 7 ES_Irs Ts 1I .T.DD, (4K + 1) } where TP. E such
{ {355)
O and lim; tr; = oc. Theeffor T 2 mmax
that ift 2 Te.D then E Ts < ct and tr, D for any 10,1).Then under the good events defined in Equation (18) and (19) we have
(M) M) F(wI) S 5c, VI M(T), I((T) + 1....,
where h(TT) -min(t E N 2 (2), V E N}. and h(T) mingt E N 12
18/m1 +2, 1 NJ.
Theorem is a by product of Lemma 3 in Wang et al. (2021) with L = D.
28

---

E Sample Complexity of FraPPE
In this section, we first derive the stopping criterion in E.1 that makes FraPPE (1 correctt Then we move on to the almost sure upper bound on sample complexity of FraPPE in E.2. Then we respectively prove asymptotic and non-asymptotic upper bound guaranties on expected sample complexity in E.3 and E.4.
E.1 Stopping Criterion
Theorem Given any bandit instance M M and a preference cone C, the Chernoff stopping rule ensure 8) -ooorreecsssss in identifying the set of Pareto optimal arms is given by
min mi, ElI: n, (yEnndd x MeA.)(M) zEc+
min
inf
min
Σ
DRL
(2 YTMMes 2 Mr) 2 c(t,
k=1
In(3 (m())
where 8) a Ekm 3lm (Nk.)) + KG
Proof. We begin this proof in two parts. First, we show that the stopping time T N finite ie. < oo and then apply concentration on the carefully chosen stochastic process by mixture martingale technique (Kaufmann and Koolen, 2021) to achieve (1 (1- corrrectess..
Finiteness of Ts. We claim that Ta 0o, if the parameters in the model converges in finite time. Specifically, for FraPPE, we say it stops when the good events defined in E.3 holds with certainty, and additionally the allocation w, has converged to the optimal allocation w" (M). While finiteness of the first event follows directly from tracking results in Appendix H (For > 4K, each arm has been played enough number of times for Mt to M; finiteness of the second event is due to convergence guaranties of the Frank Wolfe iterates proven Appendix D.
Stopping threshold.
We define the following stochastic process (4 Σx ma mi;)) minl mingge+ DRL (z M MR
3 In
In N..)). Now MM belongs to exponential family of distributions, z z Mr also belongs to the exponential distribution with linearly projected scalar mean. Thus, we can directly apply the mixture of martingale technique i.e. Theorem of (Kaufmann and Koolen, 2021) (Refer Theorem 13) with our definition of (() to conclude the proof.
E.2 Almost Sure Upper Bound on Sample Complexity
Theorem 7, For any M E M. and (0, 1), stopping time of the algorithu FraPPE satisfies
T8 log(5)
limsup 8-50
S TM.C and Ta < 00,
almost surely.
Proof. This proof structure closely follows Appendix I of (Wang et al., 2021) with adaptations necessary due to vector valued rewards ordered via given preference cone C.
We start the proof defining the event
E è (F(w: M) F(w* + oo)
We claim that E\t is sure event following Theorem 5 and periodic forced exploration used in FraPPE (So every arm is pulled infinite times, thus we leverage theory of large number). Since we have proved continuity of F(w] M,) with respect to M, we can further claim F(w, M,)) - ([w((M) M) as t + We again assume existence of to E N such that for t > to.
29

---

F(wi MM) 2 (1 (M) M) for e E (0, 1). We also assume existence of constants
ai (M) > 0 such that if vI 2 ci (M), ((1, s log co(M)) Therefore the stopping time
75 = infft foo) MD) 2 3(t,
s inf(t > to : t(1 - c) (M) M) 2 B(t,
s inf max (1M)) max :t2 log(cz(M)1))
(1-c)6 TMee
- T8 sa( + to + TM.e
log [cc((M)TM.e'
(c(MM)Tmee)) (1 (1-6)ō
)
+ log log
(1 (1-e)ō
(1 6)-
where the last inequality holds due to Lemma 12.
This result ensures asymptotic optimality of FraPPE, i.e, for all 5 E (0,1), lim sups-0 log( TM.c and also TΦ < oo almost surely.
E.3 Expected Upper Bound on Sample Complexity
Lemma 2 (Sample Complexity Upper Bound), For any M E M, E, E (0,1) and ó E (0, 1), and
preference cone C, expected stopping time satisfies limsupp-0
Blad
< (1 + ε) T 66
log
Proof. Definition of Good Event. We define our good events as Gi(T) & Ni=Mo) G1(t) and G2(T) A Ni=A(1) G2(,), where
(t) A
min xεåx hel PC1M) 1770)
max
(x (x-ui -- -6>
min xε heHp( Mi(0--19))
max
xx- wi h}
(18)
G2(1) = {M. E S. SEAAEIAIIIWAAA - F(w) <e, Vo AKr}
(19)
We start by declaring existence of some constants. Let ITDD E N such that if 2 TepD then E. Ts < el and Ir. > D for any E 1).
Following the concentration results in Appendix F, we can show that G1(t) n G2(() holds true, and thus, by Theorem 5, for 2 h(T):
(M))(M) F(we|M) 5c.
Here, h(T)- = minft E N T2/11((T, / & E N}. h(T) = minft E N 78/11 +2, / K E N). and T > max 35D 11 T (4K + 3.
Now, given (t) n Gt( holds true, we have min (T, S ((T) + Ei=nory 1(7 > T), where is the stopping time of FraPPE, Thus,
mi < ((T))
Σ (Tb(T)
11F[(w: M.) ot,
Now, for t > T(T),, F(we) | M.) < F(we M) < (MW)) 6e.
30

---

Therefore, we have,
c(T,8)
min( h(T)+
(MT))) 6e) < c(t,8)) - h(T) (=h(T)
Σ
F(wr+(M)
Finally, we define a constant
cT,6) S ST}. To(d) & inf[T E h(T) + F(wr (M) 6E
Now, we introduce small constant é (0, 1). such that T h(T) 2 1+z when T (3) This
T
choice of é is reflected in non-asymptotic sample complexity upper bound (Lemma 6 in Appendix E.3).
Now, following the algebra in (Wang et al., 2021), we gel
35D
E [al I
+ T
+ (4K + 1) Tb())) +
Σ P((G((T)GG(TT)) (20)
C.D
T=N+1
where N max
35D)
+
T G,D.
T.D:s (4K + 1) and To(d) satisfies the following inequality
11
( 1a
(6) S max
I+ē
1
log
+ log log
(lw M) 6e
(1 + E)02(M)
log
(M(w)(() IM 6e) (1+ ()e((M)
+ log log
(F(w((M) M) 6E)
Thus, the asymptotic sample complexity is then given by,
E E[ra]
1+2
lim sup 8-+
I
log(})
(M) M) 6e
Optimality follows if and ? are arbitrarily small, that is lim sups-00 log(?) Hence, proved.
B|Ta] S F(w)())) TT.cc
L
E.4 Non-Asymptotic Sample Complexity Upper Bound
Lemma 6. For any M E M, e, E (0, 1) and 8 E (0, 1), and given preference cone C stopping time of the algorithm FraPPE satisfies
[(ra]
34c K
k=1
DKL (Z Mr 20 TTx Mx)
19/4
DKL (Z Mr.
2
2TTTax M&) 19/4
35D
11
+ max (())) {
11
(4K+1) + +1) 11
+
1+E
log
((F(w*(M) M) ( + log log
(1 (M)
(1 (1+6)02(MM) ((F(w>(M) M) - Ge)
+ F(we (M)
M) 6e
Proof. We combine Equation (20) and Lemma to write the expression of expected sample com- plexity and conclude the proof.
31

---

Concentration Result
Lemma 7. Under the good events defined in (18) and (19),
P ((CC(()) 00
Proof. We first remind the definition of the good events
G1(t) _
max xEAx he PW
min
(x w:-1, -6> max xEAx heHF(. M1
min
(x- w, h)
G2(t) = Mr E S.A SSAAIF(WMM)) F(WIM) <,, ww E AKr}
We have (t) {IIM - M Mo-1lloo.c I Ere} and also G2(() C {IlM Melloo.00 S Eaet if we
apply Theorem and Corollary respectively.
Then have
P ((CG(T))G)((T) S
P(I M, Melloo,00 Ec)
k(T)
where & max(f1,er&2 (2,c) Now ||M M, Mol,oc,00 max max 2 TM M,). Therefore
T
P P(GG(())22(T))
Σ h(t))
P(max max 2 TM (M-) > Ex) =EC+ KE[K]
T
K
P max z (Mz - Me,,) > Ec)
zEc+
h(t))
From tracking results (Lemma 9) we have at any time > 4K and Vk E [K]. Ne, 2 V k K,
ensuring that each arm, is played enough till time / (T) to bring Mr, close to Mg. Now we choose
Zmax A arg max Iz Mr MR.el- Therefore
(I(T)))))))
P (Z
(M₃ (Mx
Mexe)) E.)
(21)
R(E) k=1
Then applying Chernoff inequality on the probability on the R.H.S of the inequality (21), we get
P lz (Mr Mr.e)l Ee S ee
[exp( v(A,) + exp( exp(-VEAt)
Dic. (Ni Mr Ece Mc) and A
DKC. (xiTa Ma Ma).
where A
We leverage this
vK upper bound the bad event get
VK
F ((((T))))))(T)))
S Sek
ΣΣ
explp +exp(-ViAtt <0
km
P (G((T)
34c
Σ
DKL (i Mr. 2TTr M,) 19/4
N=N
k=
(22)
DKL (I My + Ee 2 Mg) 19/4
Where the last line is implied by leveraging Lemma with a 3. :3 2 and A A A respectively.
32

---

Now using Theorem 8 and 9 of Wang et al. (2021), we also get stricter versions of Theorem 3 and Corollary
Corollary 5. (Stricter version of Corollary 4) For any M E M and 6 < (0, where k - inf,, inf inf endr)mnd((m)) z (TT;; TT)) then if |M - Mloo..0 I 2D then
[F F() < c, Yo E AKT
Theorem 8. (Stricter version of Theorem 3) Let M E M and e (0, For any r & (0, 1), and w E A M E Se that is || Mllac, I 2D. then we get
min (x- w, w. xeAx h (w.r)
max min (x- w, xEAx (w.
< V(w,r) E ARn (0,1)
2'
and
min (x w. h) (w.r)
min (x w, w,h) (eHHi(.rr)
< < v(w,,,,) E ARy (0.1) AK
Therefore putting & probabilities as
2D in Equation (22) to get the final non-asymptotic bound the bad event
P((a(T))))()) s 34cK
K
A= DEL (Z Mr
2
2 My.
19/4
1
DKL. (Ztrax Mr
20
m Mi) 19/4
33

---

G Algorithmic Complexity
G.1 Time Complexity
1. Pareto Set Estimation. Our proposed algorithm FraPPE first computes the set of Pareto arms based on current estimates of the means. We refer Kone al. (2024) to state that worst-case complexity for estimating Pareto set is given by O (K log(K) log(K)mux(1,1-22
2. Now for each candidate pure Pareto policies and its neighbour,
(i) Frank-Wie Wolfe Step. FraPPE again solves a linear optimisation as a part of Frank- Wolfe update step in the sub-differential set. So, it also suffers complexity of O tol due to K-independent upper bound on curvature constant.
(it) Stopping Criteria. To calculate the GLRT metric FraPPE solves another linear optimisation with complexity O tol since z and respectively come from a convex preference cone and its polar form.
Therefore Step 2 suffers from a total time complexity of O K Kiln/KLL. tol
since in the worst case,
there can be Pareto candidates and there can be min K, [.] neighbours.
Parameter Update. Updating Me+1 enjoys complexity of order O(L).
Total Time Complexity. Then combining Step 1, and we get the total worst-case time complexity per iteration of FraPPE as O (K ) + O KL (K.)) O(L)
O (max {K (Klog(k (ogg())mxffta
K min(K, L}}).
In most real-life instances, the number of available options greater than objectives, i.e K L. In that case FraPPE enjoys time complexity of O (KT2), which a significant improvement over existing literature. Notably, the complexity shows that the complexity for calculating the Pareto front dominates the overall complexity when I. 2 5 and K 2 19.
G.2 Space Complexity
We compute the space complexity of FraPPE in three steps,
Mean estimates. We need to maintain the estimate of M of dimension L per step, so space complexity is of OKLL).
Estimated Pareto Set. This is of O(K) in the worst case.
Neighbour set. The space for maintaining the neighbour set of O(KL).
Total Sample Complexity. Therefore the total space complexity of FraPPE is given by O(KL).
34

---

H Tracking Results
We leverage similar tracking results Wang et al. (2021). We reiterate the Tracking Lemmas again with notations used in this paper.
Lemma 8. Let {as)SeN E Ax be sequence of vectors such that Ty is ej for h = [1, Kj. Then
1 = NK,t=
E. [1, where NR. Σ 1(A, = k}
V1 2 K + E arg max
NW
where the arg max breaks ties arbitrarily. Then for all t 2 K, and all & E []
Σ The - 5) S
Σ
xbas +
==1
a=1
Lemma 9. At any 2 4K, the sampling rule of FraPPE satisfies wa E
2VTK
Proof. By forced exploration enforced in FraPPE, write
1
tw
T2 (x,
1/K, ..... 1/K)}
K
12 1 1
K
2
K
2 2
K
2vtK
35

---

I Additional Experimental Details
L.1 Implementation Details
Computational Resource. We run all the algorithms on a 64-bit 13th Gen Intel octa-Core 17-1370P X 20 processor machine with 32GB RAM.
This real-life inspired data contains tabulated entries of phase-2 booster trial for Covid-19 (Munro et al., 2021). Cov-Boost has been used as benchmark dataset for evaluating algorithms for Pareto Set Identification (PSI). It consists bandit instance with 20 vaccines, i.c. arms, and 3 immune responses as objectives, i.c., K 20 and L = 3. Additionally, Kone et al. (2024) provides detailed description of this dataset in Table (empirical arithmetic mean of the log- geetrransformed immune response for three immunogenicity indicators) and 4 (pooled variances). For entirety, we include the mean and pooled variance table here
Dataset Description: Cov-Boost.
Table Mean matrix
Dose 3 (booster)
Immune response
Dose 1/Dose
Anti-spike IgG
5T
cellular response
ChAd
9.50
6.86
4.56
NVX
9.29
6.64
4.04
NVX Half
9.05
6.41
3.56
BNT
10.21
7,49
4.43
BNT Half
10.05
7.20
4.36
Prime BNT/BNT
VLA
8.34
5.67
3.51
VLA Half
8.22
5,46
3.64
Ad26
9.75
7.27
4.71
m1273
10.43
7.61
4.72
CVn
8.94
6.19
3.84
ChAd
7.81
5.26
3.97
NVX
8.85
6.59
4.73
NVX Half
8.44
6.15
4.59
BNT
9.93
7.39
4.75
BNT Half
8.71
7.20
4.91
Prime ChAd/ChAd
VLA
7.51
5.31
3.96
VLA Half
7.27
4.99
4.02
Ad26
8.62
6.33
4.66
m1273
10.35
7.77
5.00
CVn
8.29
5.92
3.87
Table 4: Pooled variances
Immune response
Anti-spike IgG
NT 50
cellular response
Pooled sample variance
0.70
0.83
1.54
36

---

Code. The anonymous repository link for the implementations code repository.
1.2 A Pseudocode of Accelerated PreTT
The algorithm PreTS provided in Shukla and Basu (2024) lacks tractability discussed before. The allocation computation involved constructing convex hull over the Alt-set, which is very expensive and makes it non-implementable. So, here we provide accelerated version of PreTS (Algorithm 2) that can be implemented leveraging our observations of the optimisation problem. Note that, this version of PreTS is still expensive to run. Roughly our Algorithm 2 runs 90 times faster than Algorithm 2 when implemented in Python3 with identical resource environment.
Algorithm Accelerated Preference-based Track-and-Stop (Accelerated PreTS)
1: Input: Confidence parameter 6, preference cone C
2: Initialise: For E [K]. sample each arm once s.t. WK ., mean estimate Mr
3: while Equation (8) is FALSE do
4: Estimate Pareto Indices: Calculate Pareto indices P. based on current estimate Mr.
5: Estimate Set of Pareto Policies: II consisting pure policies with in E Pe basis.
6: Set of Neighbours: II II? where II is the set all pure policies.
min min Σ WE (x Ma, || 27 Ms) T (n)n)((r))) (M) =ec+ m, (
7: Allocation: We f- arg max min WEAR
8: C-tracking: Play A, min Na.: - E W, (ties broken arbitrarily)
9: Feedback and Parameter Update: Get feedback R2 E RR and update Me to Me+1 with R
10: end while
Recommendation Rule: Recommend P; as the Pareto optimal
37

---

Runtimo iteration scconda)
2
30.6-2
K- 40.6
Runtimee teeration
K=
Kw20
K=
100
200
300
400
500
Time step
Figure Runtime per iteration (in seconds) of FraPPE for varying number of arms K in the Gaussian instance with L 2 and correlation coefficient 0.9.
J Runtime Analysis of FraPPE
In this section, we provide runtime analysis of FraPPE with varying values of K and L.
Scaling with K. We consider synthetic environments consisting L 2, multivariate Gaussian rewards, and positive right orthant the preference cone. Additionally, we assume the two objectives to highly positively correlated with correlation coefficient p = 0.9. We set we vary the number of arms K = 5, 10, 20, 30, 40, keeping the Pareto front same and report the corresponding clock time per iteration for each the instances. The final results are averaged over 10 experiments.
0.01. Finally,
Observation. From Figure 6, the trend in runtime sub-linear with respect to K, i.c. the clock runtime complexity scales with at most O(K).
Scaling with L. To test the runtime of FraPPE with varying values of L, we fix K = 25. Keeping all other parameters and Pareto front same, set four environments with L -= 2, 6, 10, 14 report the runtimes per iterations. The final results are averaged over 10 experiments.
Observations: It is clear from Figure that both mean and median runtime of FraPPE falls below the rate O(log( K) max(1,L-2)) after T, 2 5. That means complexity of calculating Pareto front dominates the complexity of lower bound optimisation.
20.0
25
Runtime Iteration (in seconds
cllogiR/r4c(11-33
K- 25.11-11
15.0
Ittratioo On
7.5
50
2.5
Lo2
Lud
Lw10
100
200
300
400
500
Time step
Figure Runtime per iteration (in seconds) FraPPE for varying number of arms in the Gaussian instance with K = 25 and correlation coefficient p = 0.9.
38

---

K Auxiliary Definitions and Results
Theorem 9 (Berge's Maximum Theorem). Let l and be topological spaces, f : u x 7 R and C u be non-empty compact set for all E u. Then, if C' is continuous (=(x) maX f(u, u) continuous and ("(u) = {o E C(u) (u) ( f(u, is upper- hemicontinuous.
Theorem 10 Coonsker-Vardhan Variational Formula). For mutual information KL(PI)Q), we have that:
dkL( = sup Ep [f] - In Egg [cxp(f))
Lemma 10 (Peskun Ordering), For any two random variables X, Y on RKL the following are equivalent:
1. Y.Y
2. For all a E F
3. For all non-negative functions S1, J,. Skk have that: II 1=14 S IT 1=14
Theorem 11 (Berge (1877)). Let X and Y be Hausdorff topological spaces. Assume that
1. 4 X = K(X) is continuous, where K(X) = {F E: S(X): FF is compact.) } (i.e. both upper and lower hemiconituous),
2. u
continuous.
Then the function + continuous and the solution multifinction 4- X - B(Y) is upper hemicontinuous and compact valued, where S(Y) is the set of non-empty subsets "f
Theorem 12 (Feinberg et al. (2014)). Assume that
1. X is compactly generated,
2. ④ X = S(Y) is lower hemicontinuous,
3. u X x Y R is K- -iinf-comppct and upper semi-continuous Grz (T).
Then the function v X + IR is continuous and the solution multifunction 4' X = S(Y) is upper hemicontinuous and compact valued.
Lemma 11 (Combes al. (2017)). Let % be metric space and Y be a nonempty open subset in R Let u X x Y + R and By u(x, y) over x E X. Set
du exists and is continuous in X x Y. For each Y, let x (y) minimises
e(y) u(=(((()))))))) (y).
Assume that x² Y + a continuous function. Then v is continuously differentiable and
v(y) = Ou (x" (v).y). dy
d
dy
Fact 7 (Existence and Continuity of Minimum). If X and Y are topological spaces and is compact. Then for any continuous f X x Y + R, the function g(x) & inf f(x, y) is well-defined and continuous. Additionally, infyey f(x, y) mingey f(z, y).
Fact 8 (inf and min Union of Sets). Let us consider ordered universe S and set A C S which is union [ sets, iee. A User A; and A C. S. the following statements are true:
1. inf A exists, and
2. 0; A inf A exists for each T,
they imply that inf E 1}. The same holds true for min.
39

---

Theorem 13 (Version of Theorem 7 in Kaufmann and Koolen (2021)), Let d > 0, v be independent one-parameter familliss with mean şa and S [K]. Then we have,
In (1)
Pv
3E N: Σ
NL (Ne,, Ma) 2
Σ aES
3ln (1 + In (Maa) + +S|ST
58.
||]
aES
11 (11()++)+) with
Here, 9: RR+
R such that g(x) 2h3/2
2
Vu 2 1, h(u)= a In(u)
Y2 E (1,e]vo 0, hz(r)= = exp (x)
(x)
h- (x)
fx22
In(=]
2(0 In(nn()))
else
Theorem 14 (Grinberg (2017)). For a subset S in Euclidean space R", the statements compact, ie every open cover has a finite sub-cover = S is closed and bounded.
Lemma 12 (Lemma 18 in (Garivier and Kaufmann, 2016)). For [1, el,e/ any two constants
c1,02
C2 c9
log
+ log log
C1
such that oıæ log (c22*))
Lemma 13 (Wang et al. (2021)), Let B (0,1) and A> 0.
r +
Jo c-p dt
dT
BA +
Example 1. Multivariate Gaussian with mean and covariance E The density function is
f(x) = (2x)= det(E)) exp (--1x- 4) x (x- 11)
We can rewrite it as
f(x) = (2T) & exp (E- + vec (-1-ー1) vec (xx 1) [log |>| + 4 E u1]
Thus, the base density h(X) (2x) 4. The natural parameter 17(0) sufficient statistic is Txx) = (vec(xx))) The log-normaliser or log-partition function is (0) = [log det ()) + 4114 14].
(veo -----)1)1-- The
Σ
x
40

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Abstract has clear mention of theoretical claims and contributions towards existing literature.
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 the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation 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: We have clearly mentioned the limitations and potential future directions of research in Section
Guidelines:
The answer NA means that the paper has 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on 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 low or images are taken in low lighting. Or speech-to-tex, 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 of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't '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?
41

---

Answer: [Yes]
Justification: The assumptions for problem environment are standard in the literature and are described in the beginning of Section 2 and in Section 4.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All experimental details are given in Section and also in supplement exten- sively for full reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is 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 novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS 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 a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a 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 or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
42

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
All the codes for experiments given with an anonymous link in the supplement.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
oeeioonollooo icy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nips. wctpublic//aeccccccccccccccc ggwii/es///////eeeeee /Ce///eeeubbiiic wttssSuubissioos. ssionPolicy) 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 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).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: 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?
Answer: [Yes]
Justification: All the dataset sources, hyperparameter details are given in Section and supplement.
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, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: This paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
43

---

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 the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. 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 figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: The computational resource details used in the experiments are reported the supplement in details.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
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 ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https //neuririsp... cc/ppblicc/thicssiiieeeee
Answer:(Yes.
Justification:
The authors have read the code of ethics and confirm that the research con- ducted the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA
that the authors have reviewed the NeurIPS Code of Ethics. If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: This research should be considered as foundation research, though it can have positive impact terms effective experimental designs in sectors like policy making, clinical trial etc as described as motivation in Section 1.
44

---

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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
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, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This research uses only open source and synthetic datasets.
Guidelines:
The answer NA means that the paper poses no such risks.
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 is 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 or 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: [Yes]
Justification: Every piece of code data used in this research has proper citations and are respected.
Guidelines:
The answer NA means that the paper does not 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, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
45

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi 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-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:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel 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 participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in 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 in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to 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: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
46

---

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 we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: Core method development in this research does not involve LLMs as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: / //neruurpp.... www.///oeeennee///000/00 for what should or should not be described.
47


Reviews:
[{"review_id": "eGKcR3Jvkj", "reviewer": "Reviewer_JNA1", "summary": "This paper addresses an open problem in preference-based pure exploration (PrePEx) in multi-objective bandits, where the goal is to identify all Pareto optimal arms under a given preference cone with fixed confidence. The authors propose FraPPE, a computationally efficient algorithm that provides an asymptotically optimal solution for arbitrary preference cones and exponential family distributions. The key contributions include: \n- Structural reductions of the optimization problem, avoiding convex hull computations, \n- Application of Frank-Wolfe optimization for efficient lower bound tracking, and \n- Theoretical guarantees of asymptotic optimality with improved computational complexity.\n- Simulation results to support the proposed results.", "questions": "**Questions**\n\n**Preference Cone Specification in Practice:** What are the real-world models with the preference cone C, and what are their typical values? Also, how sensitive is the algorithm's performance to misspecification of the preference cone C? In real applications, domain experts may have uncertainty about their preferences. Have you considered extensions where the cone is learned or refined during exploration?\n\n**Computational Bottlenecks:** Despite the theoretical improvements, conic programs per iteration could still be computationally demanding. Does an experimental time breakdown on which steps of the algorithm provide the time bottleneck make sense?", "limitations": "It would be great if the authors added a dedicated `limitations` section discussing the points touched upon in the Weaknesses and Questions section.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n\n**Novel Theoretical and Algorithmic Contributions:** The paper makes significant progress on an open problem posed by Crepon et al. (2024) by providing a computationally efficient and asymptotically optimal algorithm for arbitrary preference cones. The decomposition of the Alt-set without requiring convex hull computations is a significant theoretical advance. The reduction from O(K²L) to O(KL min{K,L}) computational complexity is non-trivial and practically important.\n\n**Problem Relevance and Motivation:** The multi-objective bandit setting with preference cones is well-motivated through concrete applications in clinical trials (COV-BOOST), material design, and RLHF. The inability to scalarize objectives a priori is a genuine challenge in these domains, making the preference cone framework particularly relevant.\n\n**Strong Literature Positioning:** The paper does a great job of placing itself amid related work. The authors clearly articulate the limitations of existing approaches: successive elimination methods that only find approximate Pareto sets, the computational intractability of PreTS, and the restriction of previous optimal algorithms to other distributions. The connection to pure exploration with multiple answers and the Frank-Wolfe literature is also well stated.\n\n**Clear Presentation:** The paper is well-structured with a logical flow from problem formulation through theoretical contributions to algorithm design. The use of illustrative examples aids a deeper understanding of the work. Technical concepts are introduced progressively with appropriate mathematical insights.\n\n**Weaknesses:**\n\n**Limited Experimental Validation:** While the COV-BOOST results are compelling, the experimental section would benefit from more ablation studies: (i) runtime breakdown to validate computational efficiency claims, (ii) scaling effects with varying K and L, and (iv) ablation studies on other parameters.\n\n**Assumptions and Practical Considerations:** The assumption of perfect knowledge of preference cones may be restrictive in practice. Maybe a discussion of robustness to misspecified cones would be a nice add.", "was_revised": true, "final_justification": "I am happy with the author's response. I would like ot retain the score. I really like the paper as it stands.", "rebuttal": "We thank the reviewer for taking time to review our work, and for appreciating the novelty and clarity of our contributions. We respond to the questions below, while we include the promising improvements in our updated draft.\n\n1. **Experimental validation and computational bottleneck:** \n\n- a. *Runtime of FraPPE:* While only using CPUs (without parallel processing and tensorization), each iteration of FraPPE takes $\\sim 64$ milliseconds/iteration for COVBOOST ($19$ arms and $3$ objectives). While for DB [1] ($128$ arms and $2$ objectives), FraPPE clocked in $\\sim 98$ milliseconds/iteration. For synthetic data with correlated objectives ($5$ arms and $2$ objectives), it takes $\\sim 14.6$ milliseconds/iteration. These results are obtained by averaging over 1000 iterations. \n\n- b. *Runtime of baselines:* The implementations available in the literature differ in their setup and programming languages: [2] uses Julia, [3] uses C++. In contrast, to make the code accessible to wider audience, we chose Python3 for implementation with only three well-known packages: Numpy, CVXPY, and Scipy. Thus, we surmise it would be unfair to compare the clock runtimes of the different baselines implementations. \nBut resonating with the reviewer's remark, we have now conducted a runtime analysis with varying $K$, $L$ to validate our theoretical claims. \n\n- c. *Conic programming:* Yes, we agree that conic programming is the computationally costliest module here. Though we believe while solving the lower bound, conic programs are unavoidable as it is required to find the Pareto for generic cones. Thus, it has been a part of the open problem posed by [2], i.e. to reduce the computational complexity per iteration up to the complexity of Pareto set computation. \n\n- d. *Larger dataset- DB [1]:* We have tested on all the datasets used in the SOTA paper for exact Pareto set identification: PSIPS [3]. We are currently testing FraPPE on the *DB (Disc Brake) dataset* ($128$ arms and $2$ objectives) that presents an efficiency and safety optimization problem in disc brake manufacturing for automotives. In the literature, larger datasets like DB are used only to attain $\\epsilon$-approximate Pareto set identification [5,6], while FraPPE aims for exact identification and succeeds as per the preliminary results.\n\n2. **Specification of the cone:** \n\n- a. *Practicality of knowing $\\mathcal{C}$:* We assume to know the preference cone following the present literature of PrePEx, where the SOTA results are mostly available for the positive orthant as the cone. Knowledge of $\\mathcal{C}$ is available in multiple real-world systems: polyhedral cones are used in *aircraft design optimisation* [7], positive orthant cone ($\\mathbb{R}^L_{+}$) are used in Portfolio optimization balancing return, risk, and liquidity [8], customised asymmetric cones are used in climate policy optimization with multiple national goals [9].\n\n- b. *Learning $\\mathcal{C}$:* We agree that sequentially learning the cone from multiple expert's feedback while exploring is an interesting problem with its own set of challenges. But if we do not know $\\mathcal{C}$ or encounter misspecification, the lower bound of [10] is not valid and we should derive a new lower bound. It is an ongoing study and we will mention it in future works.\n\nWe hope that our response have addressed the concerns and questions. We remain available for further discussion.\n\n**References:**\n\n[1] Tanabe, R. and Ishibuchi, H. (2020). An easy-to-\nuse real-world multi-objective optimization problem\nsuite. Applied Soft Computing, 89:106078.\n\n[2] Crepon, E., Garivier, A., and M Koolen, W. (2024). Sequential learning of the Pareto front for\nmulti-objective bandits. PMLR.\n\n[3] Kone, C., Jourdan, M., and Kaufmann, E. (2024). Pareto set identification with posterior sampling.\n\n[4] Ararat, C. and Tekin, C. (2023). Vector optimization with stochastic bandit feedback. In PMLR.\n\n[5] Karagözlü, E. M., Yıldırım, Y. C., Ararat, C., and Tekin, C. (2024). Learning the pareto set under\nincomplete preferences: Pure exploration in vector bandits. In PMLR.\n\n[6] Bradley, R. A. and Terry, M. E. (1952). Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika.\n\n[7] Mavrotas, G. (2009). Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems. Applied Mathematics and Computation.\n\n[8] Ehrgott, M. (2005). Multicriteria Optimization. Springer.\n\n[9] Keeney, R. L., & Raiffa, H. (1993). Decisions with Multiple Objectives: Preferences and Value Trade-Offs. Cambridge University Press.\n\n[10] Shukla, Apurv, and Debabrota Basu. \"Preference-based pure exploration.\" Advances in Neural Information Processing Systems 37 (2024): 17313-17347."}, {"review_id": "ty23VMf6lj", "reviewer": "Reviewer_cohg", "summary": "This paper considers pure exploration in a K-armed stochastic bandit problem with L-dimensional rewards. The goal is to identify the Pareto set of policies (distributions over arms) given a fixed confidence level in as few evaluations as possible. The paper builds an approach based on the lower bound on Pareto front identification. Using structural properties, it forms a computationally tractable alternative to the minimax optimization problem in the lower bound. A track-and-stop inspired arm selection and stopping rule is proposed based on the tractable lower bound. Asymptotic optimality of the proposed rule is established. Experiments are carried out to show how the proposed rule compares with SoTA.", "questions": "1) It is hard to parse the contribution of Section 3.3. What is the exact reduction in computational complexity when the polar cone representation of alternating instances is used? \n\n2) Please elaborate on how the $ L$-parameter exponential family extends the scalar exponential family. What conditions are required on functions $h$, $\\eta$, and $T$?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n\nThe paper is clearly written. The authors did a good job of explaining this complicated pure exploration problem in nine pages. \n\nThis paper solves an important open problem in bandit-based vector optimization by proposing a computationally efficient, asymptotically optimal, fixed-confidence pure exploration algorithm. The proposed algorithm utilizes a tractable reformulation of the intractable optimization problem. Theoretical analysis of the computational complexity demonstrates a significant improvement over existing approaches. The paper proposes a non-asymptotic, asymptotically optimal bound on the sample complexity. Experiments support theoretical claims. \n\n\nWeaknesses: \n\nThere is no major weakness.", "was_revised": true, "final_justification": "The authors have sufficiently addressed my comments regarding clarifications. This is solid work. Please incorporate these clarifications in the final version of the paper.", "rebuttal": "We thank the reviewer for acknowledging our work and taking their time to review. We respond to the questions raised below:\n\n1. **Section 3.3 :** In this section, we leverage the structure of the alternating instance $\\tilde{M}^{L \\times K}$ to gain computational efficiency for the two innermost minimisation problems in Equation (3). \n\n- (a) Direct optimisation over $\\tilde{M}^{L \\times K}$ can have complexity $\\mathcal{O}(KL)$, since optimising an $L$-dimensional vector inside a cone has complexity $\\mathcal{O}(L)$. With the polar cone representation of the alternating instances (Proposition 1), $\\tilde{M}$ can be expressed with $\\boldsymbol{y}, \\boldsymbol{\\pi}_i^{\\star}, \\boldsymbol{\\pi}_j $. Here, $\\boldsymbol{y}$ is an $L$-dimensional vector on the boundary of the polar cone of the given preference cone $\\mathcal{C}$. Thus, for a fixed $\\boldsymbol{\\pi}_i^{\\star}$ and $\\boldsymbol{\\pi}_j$, we now optimise over an $L$-dimensional vector rather than a $L\\times K$ matrix. \n\n- (b) Further with this reduction, we observe that $\\boldsymbol{z}^L$ and $\\boldsymbol{y}^L$ are defined on the cone $\\mathcal{C}$ and its polar cone $\\mathcal{C}^{\\circ}$. Thus, any efficient second order conic program solver (for e.g., CVXPY) can solve both the optimisation problems in $\\mathcal{O}(L)$ rather than $\\mathcal{O}(L^2)$. \n\n\nHence, the total computational gain achieved in Section 3.3 is  $\\mathcal{O}(KL^2) \\rightarrow \\mathcal{O}(L)$.\n\n\n2. **L-parameter exponential family:** Since we adopted the standard definition of multi-parameter exponential family from statistics ((Chapter 18 in [1])), which is also a generalisation of multivariate Gaussian of dimension $L$ with mean $\\boldsymbol{\\mu}$ and covariance $\\boldsymbol{\\Sigma}$, we omitted a detailed discussion. Thanks for the remark. We clarify it here and must add the details with the extra page available. \n\n- *Definition:* Specifically, let us consider an exponential family defined as $f(\\boldsymbol{X}\\vert\\boldsymbol{\\theta}) := h(\\boldsymbol{X}) \\exp\\left( \\langle \\eta(\\boldsymbol{\\theta}), T(\\boldsymbol{X})\\rangle - \\psi(\\boldsymbol{\\theta})\\right)$ with $\\boldsymbol{\\theta} \\in \\Theta \\subseteq \\mathbb{R}^L$ and $\\boldsymbol{X} \\in \\mathbb{R}^L$. Then $\\eta : \\Theta \\rightarrow \\mathbb{R}^s$ is the natural parametrization for some $s \\geq L$. $T : \\mathbb{R}^L \\rightarrow \\mathbb{R}^s$ is the sufficient statistic for the natural parameter. $h(\\boldsymbol{X})$ is the base density such that $h: \\mathbb{R}^L \\rightarrow [0,\\infty)$. Finally, $\\psi(\\theta) = \\log \\left( \\int_{\\mathcal{X}} h(\\boldsymbol{X}) \\exp\\left( \\langle \\eta(\\theta), T(\\boldsymbol{X})\\rangle \\mathrm{d}\\boldsymbol{x}\\right) \\right)$ is the log-normaliser or log-partition function. It is fully defined by $\\eta$, $T$ and $h$. Specifically, the valid natural parameters are the ones for which $\\psi(\\eta(\\theta))$ remains finite.\n\nWe hope that our response have addressed the concerns and questions. We remain available for further discussion.\n\n\n**Reference:**\n[1] DasGupta, Anirban. \"The exponential family and statistical applications.\" Probability for Statistics and Machine Learning: Fundamentals and Advanced Topics. New York, NY: Springer New York, 2011. 583-612."}, {"review_id": "sZoueZ4PlX", "reviewer": "Reviewer_6Msu", "summary": "This paper tackles Preference-based Pure Exploration (PrePEx) in multi-objective bandits, aiming to identify the Pareto-optimal arms efficiently and confidently. The authors propose FraPPE, a computationally efficient and asymptotically optimal algorithm that leverages structural reductions, a Frank-Wolfe optimizer, and a novel stopping rule. Empirical results demonstrate gains in sample efficiency and stability over prior methods.", "questions": "Can the same approach (FraPPE) be extended or scaled to combinatorial pure exploration problems, such as combinatorial bandits?\n\nHow sensitive is FraPPE to mild deviations from its theoretical assumptions in practical scenarios?\n\nCould the authors report or discuss FraPPE's actual runtime in wall-clock seconds (rather than just iteration or sample complexity), especially on the real-world dataset? This would provide practical insight into computational efficiency beyond theoretical complexity.", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n•\tThe paper tackles an interesting and well-motivated problem; namely preference-based pure-exploration.\n\n•\tThe works proposes a practical approach which reduce the computational complexity of solving the tackled problem.\n\n•\tThe paper results are supported by theoretical guarantees and empirical analysis on both synthetic and real-world problems.\n\n\n**Weaknesses:**\n\n•\tAdditional tests on larger-scale or more diverse real-world settings would strengthen the empirical claims.\n\n•\tFor clearer presentation and better contrast with prior work, it would be helpful to summarize the main differences and contributions in a comparison table. \n\n•\t(minor) While multi-armed bandits provide a foundational framework for studying sequential decision-making under uncertainty, describing them as the \"archetypal setup\" of reinforcement learning is somewhat misleading (line 36). Bandits represent a simplified special case without state transitions or delayed consequences, which are central features of reinforcement learning.", "was_revised": true, "final_justification": "My concerns have been addressed, and I have decided to raise my score to 5.", "rebuttal": "We thank the reviewer for their valuable review and remarks. We respond to the concerns raised below:\n\n1. **Experimental validation and computational bottleneck:** \n\n- a. *Runtime of FraPPE:* While only using CPUs (without parallel processing and tensorization), each iteration of FraPPE takes $\\sim 64$ milliseconds/iteration for COVBOOST ($19$ arms and $3$ objectives). While for DB [1] ($128$ arms and $2$ objectives), FraPPE clocked in $\\sim 98$ milliseconds/iteration. For synthetic data with correlated objectives ($5$ arms and $2$ objectives), it takes $\\sim 14.6$ milliseconds/iteration. These results are obtained by averaging over 1000 iterations. \n\n- b. *Runtime of baselines:* The implementations available in the literature differ in their setup and programming languages: [2] uses Julia, [3] uses C++. In contrast, to make the code accessible to wider audience, we chose Python3 for implementation with only three well-known packages: Numpy, CVXPY, and Scipy. Thus, we surmise it would be unfair to compare the clock runtimes of the different baselines implementations. \nBut resonating with the reviewer's remark, we have now conducted a runtime analysis with varying $K$, $L$ to validate our theoretical claims. \n\n- c. *Conic programming:* Yes, we agree that conic programming is the computationally costliest module here. Though we believe while solving the lower bound, conic programs are unavoidable as it is required to find the Pareto for generic cones. Thus, it has been a part of the open problem posed by [2], i.e. to reduce the computational complexity per iteration up to the complexity of Pareto set computation.   \n\n- d. *Larger dataset- DB [1]:* We have tested on all the datasets used in the SOTA paper for exact Pareto set identification: PSIPS [3]. We are currently testing FraPPE on the *DB (Disc Brake) dataset* ($128$ arms and $2$ objectives) that presents an efficiency and safety optimization problem in disc brake manufacturing for automotives. In the literature, larger datasets like DB are used only to attain $\\epsilon$-approximate Pareto set identification [5,6], while FraPPE aims for exact identification and succeeds as per the preliminary results.\n\n**Comparison table:** This is indeed a very nice suggestion. With the extra available space, we will definitely include a table that summarises the complexity of different approaches to solve Pareto set identification and their corresponding complexity. \n\n**FraPPE in Combinatorial Bandits:** We think like most of the algorithmic framework that exists for solving pure exploration in multi-objective bandits, for e.g., successive arm-elimination [1] or Bayesian posterior sampling based [2] etc., FraPPE can also be extended to solve pure exploration in combinatorial bandits. That means the goal will be to identify the optimal combinatorial or subset of arms among $2^K$ possible subsets (Or a policy with basis consisting pure policies corresponding optimal subset of arms) that maximises the reward . Additionally, the agent will observe feedback for each of the arms in the subset chosen to play at any time step. Although we think this problem is more complex due to exploration among exponentially large $2^K$ options rather than usual $K$ actions. This bottleneck calls for careful adaptation of the existing lower bound to the combinatorial setup (that might depend on complexity of differentiating between the optimal subset and the second best subset of arms). Still, this problem seems solvable by adapting FraPPE directly with necessary extensions.   \n\n\n**Mild deviations in theoretical assumptions:** The only two assumptions that we require are: the knowledge of the cone $\\mathcal{C}$ and the reward distribution being in an exponential family with non-zero second moment. The first one is a fundamental requirement as the lower bound of [6], which is our starting point, requires this. If we have a misspecified cone, the algorithm would still run and identify a part of the Pareto optimal arms but we cannot theoretically say anything about correctness and optimality. The second one is more of a theoretical requirement to prove optimality of FraPPE. The lower bound and the algorithmic technique would work for any distribution. But since the GLRT stopping rule is known to be tight for exponential families, not only FraPPE but any lower bound-driven pure exploration algorithm [7,8,9] even in simple best arm identification assumes an exponential family to prove optimality [1,2,6]. \nIn brief, we can run FraPPE for instances deviating from these assumptions but we cannot guarantee the theoretical goodness any more.\n\nWe hope that we have addressed all the concerns. We are eager to discuss further if the reviewer has more concerns or comments. \n\n\n**References:**\n\n[1] Crepon, E., Garivier, A., and M Koolen, W. (2024). Sequential learning of the Pareto front for multi-objective bandits. AISTATS.\n\n[2] Kone, C., Jourdan, M., and Kaufmann, E. (2025). Pareto set identification with posterior sampling. AISTATS.\n\n[3] Tanabe, R. and Ishibuchi, H. (2020). An easy-to-use real-world multi-objective optimization problem suite. Applied Soft Computing, 89:106078.\n\n[4] Ararat, C. and Tekin, C. (2023). Vector optimization with stochastic bandit feedback. In PMLR.\n\n[5] Karagözlü, E. M., Yıldırım, Y. C., Ararat, C., and Tekin, C. (2024). Learning the pareto set under incomplete preferences: Pure exploration in vector bandits. PMLR.\n\n[6] Shukla, Apurv, and Debabrota Basu. (2024). Preference-based pure exploration. NeurIPS.\n\n[7] Garivier, A. and Kaufmann, E. (2016). Optimal best arm identification with fixed confidence. COLT.\n\n[8] Wang, P.-A., Tzeng, R.-C., and Proutiere, A. (2021). Fast pure exploration via Frank-Wolfe. NeurIPS.\n\n[9] Degenne, R., Ménard, P., Shang, X., and Valko, M. (2020). Gamification of pure exploration for linear bandits. ICML."}, {"review_id": "wjKLzgIT8d", "reviewer": "Reviewer_aS4F", "summary": "This paper investigates the design of computationally efficient algorithms for the preference-based pure exploration problem. The authors reduce the corresponding lower-bound optimization problem into a computationally tractable form and solve it using the Frank-Wolfe algorithm. The authors further provide theoretical guarantees for proposed algorithms on computational and sample complexity. Both theoretical results and empirical experiments demonstrate the superiority of their proposed algorithm.", "questions": "Please see the strengths and weaknesses section.", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n1. This work explores a computationally efficient algorithm for solving the preference-based pure exploration problem. It presents a rigorous theoretical analysis on both the computational and sample complexity of the proposed method. \n\nWeaknesses: \n1. In the problem formulation part of Section 2, the definition of the reward distribution $\\nu_a$ seems somewhat unconventional, as the authors only define its mean $\\boldsymbol{\\mu}_a$. In contrast, (Shukla and Basu, 2024) further define the corresponding covariance matrix $\\Sigma$ to account for noisy feedback. \n\n2. In Figure 1, the authors intend to illustrate how the Pareto frontier varies under different preference cones. However, in Figure 1, the two Pareto frontiers overlap, which easily confuses readers. The authors could consider plotting the Pareto frontiers for both $\\pi/2$ and $\\pi/3$ cones to better illustrate the difference. \n\n3. Some concepts are used without formal definitions, such as the term \"stationary policies\" in line 209. \n\n4. In line 298, the authors claim that the Frank-Wolfe algorithm can handle non-smooth optimization objectives by constructing the corresponding $r$-sub-differential set. Can this approximation method guarantee recovery of the original optimal solution? In addition, please justify the choice of the hyper-parameter $r_t$. \n\n5. A minor writing suggestion: in line 205, the concept of $p$ pure policies has not been formally introduced. To avoid potential confusion, it is advisable to use the notation \\Delta_K \\setminus \\{\\pi^*\\} rather than \\Delta_K \\setminus \\{\\pi_i^*\\}. \n\n6. It is recommended that the authors provide a comprehensive table comparing different preference-based pure exploration methods in terms of algorithmic complexity (including time and space complexity) as well as the upper bounds on sample complexity. This would help readers better understand the strengths and weaknesses of the proposed method in a broader context.\n\n7. The authors could elaborate more on the technical challenges in accelerating algorithms solving the preference-based pure exploration problem, and clarify the theoretical contributions of their proposed approach.", "was_revised": true, "final_justification": "My concerns have been addressed during the discussion. I keep my positive score.", "rebuttal": "We thank the reviewer for reviewing and acknowledging our work. We respond to the concern raised below:\n\n**Covariance matrix:** In the problem formulation, we did not highlight the covariance matrix of reward distribution as it is known in our setup and the main challenge in bandits is the means of the reward distributions being unknown. \nIt is also reflected in the derivation of the lower bound in [1].\nNote that, we also consider the reward distributions can have higher moments. \nIn Assumption 1, we adhered to the definition of a multi-parameter exponential family (Chapter 18 in [2]), where $\\psi(\\eta(\\boldsymbol{\\theta}))$ is the log-partition function and $\\eta$ is the natural parametrisation. If we differentiate $\\psi$ w.r.t. $\\eta$, we get the mean $\\boldsymbol{\\mu}$, and the second-order derivative $\\nabla_{\\eta(\\boldsymbol{\\theta})}^2 \\psi(\\eta(\\boldsymbol{\\theta}))$ yields the covariance matrix. \nWe will explicitly mention the covariance in Section 2 to avoid any confusion around the definition. %\\todo[inline]{Section 2 he said, change this writing.}\n\n**Figure 1:**  Thank you for pointing this out. Although the intend was to show that different preference cone results in different Pareto optimal arms, but they can have intersection. We will change it such that there are no intersections so that it is more clearly understandable.\n\n**Stationary policy:** By stationary policy, we wanted to convey that the pure policies (stands for playing an arm) does not change over time. We will definitely include a formal definition. \n\n**Line 205:** We will formally define pure policies (policies that have all the probability mass on a single arm). Thank you for pointing this out.\n\n**Choice of $r_t$:** As per the existing literature on Frank-Wolfe [3], the approximation parameter $r_t$ should shrink at a rate $\\Omega(1/t)$. It ensures the convergence of empirical allocation $\\boldsymbol{\\omega}_t$ to optimal allocation $\\boldsymbol{\\omega}^{\\star}(M)$ (Theorem 5). In practice, we have chosen $r_t = \\frac{K}{t^{0.9}}$. \n\n**Convergence of sub-differential set:** First, we prove continuity of the mapping from allocation policy to sub-differential set in Corollary 1 (Appendix D.2). Then, we show the convergence of Frank-Wolfe iterates (Equation (7)) while we iteratively optimise over the allocation policy (Appendix D.3).\n\n**Comparison table:** This a very nice suggestion. With the additional available page, we will definitely include a table that summarises the complexity of different approaches to solve Pareto set identification and their corresponding complexity.\n\n**Contribution and technical challenges:** In this paper, we successfully address the open problem posed in [4] to propose the first computationally efficient and asymptotically optimal algorithm, that works for arbitrary preference cones and exponential family distributions, and also achieves the lowest sample complexity and probability of error for identifying the exact set of Pareto optimal arms. We mention all our contributions in line 88 to 107 in the main manuscript. The key technical challenges are discussed in the beginning of Section 3.1 and Section 3.2, i.e., solving optimisation over alternating instance and Pareto optimal policy set. Complying with the reviewer's remark, we will again summarise the technical challenges tackled in this work.  \n\n\nWe hope that we have addressed all the concerns. We are eager to discuss further if the reviewer has more concerns or comments. \n\n\n\n**Reference:**\n\n[1] Shukla, Apurv, and Debabrota Basu. (2024). Preference-based pure exploration. NeurIPS.\n\n[2] DasGupta, Anirban. \"The exponential family and statistical applications.\" Probability for Statistics and Machine Learning: Fundamentals and Advanced Topics. New York, NY: Springer New York, 2011. 583-612.\n\n[3] Wang, Po-An, Ruo-Chun Tzeng, and Alexandre Proutiere. \"Fast pure exploration via frank-wolfe.\"\nAdvances in Neural Information Processing Systems 34 (2021): 5810-5821.\n\n[4] Crepon, E., Garivier, A., and M Koolen, W. (2024). Sequential learning of the Pareto front for\nmulti-objective bandits. PMLR."}, {"review_id": "qiNyUDGe95", "reviewer": "Reviewer_eLPG", "summary": "This paper studies the Preference-based Pure Exploration (PrePEx) problem, focusing on identifying the set of Pareto optimal arms in a vector-valued bandit. In this problem, the reward vectors are ordered using a given preference cone $\\mathcal C$. The authors propose an algorithm based on a computationally tractable reduction of the minimization problem and the Frank-Wolfe optimizer. They prove both the algorithm's sample and computational complexity to demonstrate its effectiveness. Additionally, the authors validate the algorithm through experiments. Results demonstrate that their algorithm has advantages in both accuracy and efficiency.", "questions": "1. My assessment suggests that the authors' definition of the L-parameter exponential family deviates from its widely accepted form. This might mean the problem the authors are solving is actually limited to one-parameter exponential families, rather than truly extending to multi-parameter ones as the framing suggests. \n\n2. Could the authors please clarify the precise definition of  $\\tilde{\\epsilon}$  in Lemma 2? Furthermore, it's not immediately clear whether both $\\epsilon$ and $\\tilde{\\epsilon}$ can be arbitrarily close to zero. Gaining clarity on these points would be crucial for me to fully assess if the algorithm achieves asymptotic optimality as claimed.\n\n\nIf the authors can address my concerns regarding Lemma 2, I would consider improving my evaluation of the paper.\n﻿\nSeparately, because I'm not deeply familiar with the Pareto Set Identification problem, I haven't been able to thoroughly check all the proofs, despite spending considerable time on them. Therefore, I'll be looking to other reviewers' insights to help inform any adjustments to my overall assessment.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n\n1. The authors design a computationally efficient and statistically optimal PrePEx algorithm that addresses the preference-based pure exploration problem with exponential family distributions.\n2. The authors provide a thorough analysis of their algorithm. Their algorithm's sample complexity and computational complexity are proven.\n3. The authors utilize real-world datasets to validate the algorithm's effectiveness experimentally.\n\n**Weakness**:\n\n1. The paper's definitions should adhere to standard, classical formulations, particularly for fundamental concepts such as partial order and the L-parameter exponential family. Regarding the latter, my assessment suggests that the authors' definition of the L-parameter exponential family deviates from its widely accepted form. This discrepancy could impact the validity of the paper's conclusions.\n\n2. Lemma 2 stands out as the most crucial conclusion in the paper. It purports to demonstrate that the algorithm achieves asymptotic optimality as $\\epsilon$ and $\\tilde{\\epsilon}$ approach zero. However, while $\\epsilon$'s definition is briefly touched upon in the appendix, the definition of  $\\tilde{\\epsilon}$ is absent. This omission prevents me from evaluating whether these two values can indeed be arbitrarily close to zero, which makes it impossible to assess the meaningfulness of Lemma 2's conclusion fully.\n\n3. The authors directly reference results from related papers for the lower bound of the problem.", "was_revised": true, "final_justification": "This paper presents a solid, technically sound approach to Preference-based Pure Exploration. The method proposed is both novel and valuable, offering a promising solution to the problem being addressed.\n\nHowever, the paper uses an existing lower bound from previous work, without providing further analysis of the lower bound under the new conditions. This leaves room for improvement in the theoretical aspects.", "rebuttal": "We thank the reviewer for taking their time to review our work. We respond to their concerns below.\n\n1. **Standard definition of partial order:** We use the classical definition of order induced by a preference cone in vector optimisation literature [6,7]. This has been used across the board in the Pareto set identification with bandit feedback literature [2,3,4,5].\n\n2. **$L$-parameter exponential family:** We think that there is a miscommunication here. Now, we include the following detailed definition of $L$-parameter exponential family in the paper. \n\n- *Definition:* Specifically, let us consider an exponential family defined as $f(\\boldsymbol{X}\\vert\\boldsymbol{\\theta}) := h(\\boldsymbol{X}) \\exp\\left( \\langle \\eta(\\boldsymbol{\\theta}), T(\\boldsymbol{X})\\rangle - \\psi(\\boldsymbol{\\theta})\\right)$ with $\\boldsymbol{\\theta} \\in \\Theta \\subseteq \\mathbb{R}^L$ and $\\boldsymbol{X} \\in \\mathbb{R}^L$. Then $\\eta : \\Theta \\rightarrow \\mathbb{R}^s$ is the natural parametrization for some $s \\geq L$. $T : \\mathbb{R}^L \\rightarrow \\mathbb{R}^s$ is the sufficient statistic for the natural parameter. $h(\\boldsymbol{X})$ is the base density such that $h: \\mathbb{R}^L \\rightarrow [0,\\infty)$. Finally, $\\psi(\\boldsymbol{\\theta}) = \\log \\left( \\int_{\\mathcal{X}} h(\\boldsymbol{X}) \\exp\\left( \\langle \\eta(\\boldsymbol{\\theta}), T(\\boldsymbol{X})\\rangle \\mathrm{d}\\boldsymbol{x}\\right) \\right)$ is the log-normaliser or log-partition function. It is fully defined by $\\eta$, $T$ and $h$. Specifically, the valid natural parameters are the ones for which $\\psi(\\eta(\\boldsymbol{\\theta}))$ remains finite (Chapter 18 in [8]).\n\n3. **Lemma 2:** Thank you for pointing this out for elaboration. \n\n- a. $\\epsilon$ is the closeness parameter necessary to define the ''good events''. These events are crucial to ensure convergence of the sequential estimation problem. In our case, the two events are (i) Convergence of the sub-differential set, and (ii) Convergence of the objective function with respect to mean estimates for any allocation policy (Equation (18) and (19)) with respect to mean estimates. \n\n- b. Although, as correctly pointed out by the reviewer, there is no formal definition for $\\tilde{\\epsilon}$, which arises as for estimating the **minimum time** required to ensure convergence of allocation policy $\\boldsymbol{\\omega_t}$ to $\\boldsymbol{\\omega}^{\\star}(M)$ and consequently $F(\\boldsymbol{\\omega_t}\\mid M)$ to $F(\\boldsymbol{\\omega}^{\\star}(M)\\mid M)$. Mathematically, $\\|F(\\boldsymbol{\\omega}^{\\star}(M)\\mid M)-F(\\boldsymbol{\\omega_t}\\mid M)\\| \\leq 5\\epsilon$ holds for $T\\geq \\bar h(T)$ (Theorem 5). Now, if $T \\geq \\left(\\frac{2}{\\tilde{\\epsilon}}\\right)^{11}$, then we get $T-\\bar h(T) \\geq \\frac{T}{1+\\tilde{\\epsilon}}$. This is a standard algebraic trick used in the existing literature (for e.g., [1]). \n\nBoth these constants can be arbitrarily small, and hence, the asymptotic optimality of FraPPE follows. We will incorporate the definition of $\\tilde{\\epsilon}$ in the updated manuscript. \n\nWe hope that our explanations clarify all the doubts regarding correctness of our results and will motivate the reviewer to adjust their score appropriately. We remain available for further clarifications and discussions.\n\n**Reference:**\n\n[1] Wang, Po-An, Ruo-Chun Tzeng, and Alexandre Proutiere. \"Fast pure exploration via frank-wolfe.\" Advances in Neural Information Processing Systems 34 (2021): 5810-5821.\n\n[2] Ararat, C. and Tekin, C. (2023). Vector optimization with stochastic bandit feedback. In PMLR.\n\n[3] Karagözlü, E. M., Yıldırım, Y. C., Ararat, C., and Tekin, C. (2024). Learning the pareto set under incomplete preferences: Pure exploration in vector bandits. PMLR.\n\n[4] Shukla, Apurv, and Debabrota Basu. (2024). Preference-based pure exploration. NeurIPS.\n\n[5] Crepon, E., Garivier, A., and M Koolen, W. (2024). Sequential learning of the Pareto front for\nmulti-objective bandits. PMLR.\n\n[6] Jahn, Johannes, ed. Vector optimization. Berlin: Springer, 2009.\n\n[7] L{\\\"o}hne, Andreas, Vector optimization with infimum and supremum, Springer Science \\& Business Media, 2011.\n\n[8] DasGupta, Anirban. \"The exponential family and statistical applications.\" Probability for Statistics and Machine Learning: Fundamentals and Advanced Topics. New York, NY: Springer New York, 2011. 583-612."}]

Author rebuttal:

Meta-review: **Summary:**  This paper focused on tackling pure exploration with preference feedback, which identify the best or an $\epsilon$-optimal item using duels rather than numeric rewards, under standard stochastic preference models. To address this challenging problem, this paper proposed FraPPE, which (i) adaptively focuses comparisons on an active set of contenders, (ii) chooses informative pairs via confidence-interval geometry to accelerate elimination, and (iii) maintains computational efficiency with incremental updates and pair selection. Theoretical performance analysis of FraPPE was presented. The instance-dependent sample complexity scales with natural hardness measures of the preference matrix. Finally, experimental results were presented to validate the performance of FraPPE.

**Strength:** 
- The problem itself is interesting and important as pure exploration with pairwise feedback is central to ranking, recommendation, and RLHF-style evaluation. 
- The design of active set and the informative pair selection are elegant, simple to be implemented in practice. 
- The performance of FraPPE is theoretically guaranteed with formal $\delta$-correctness and the instance-dependent complexity bounds. The analysis highlights the role of preference gaps.
- The performance of FraPPE is further validated via experiments including comparisons to baselines in several key metrics. 

**Weakness:** 
- The performance guarantees rely on standard stochastic preference assumptions. This paper could further discuss robustness when these are violated.
- While instance-dependent bounds are valuable, this paper could clarify the gap to known minimax lower bounds (tightness) and when FraPPE might be suboptimal in adversarially hard instances.

**Reasons for acceptance:** This paper demonstrated clear contributions from both theory and practice. The proposed FraPPE advances the state of the art for preference-based pure exploration with a design that is simultaneously fast, sample-efficient, and analyzed.

**Discussion \& rebuttal assessment:** Reviewers reached a consensus that this is a solid work with interesting problems, nice algorithm design, theoretical sound performance guarantees and experimental validations.
Decision: Accept (poster)