Constrained Pareto Set Identification with Bandit Feedback
Authors: Cyrille Kone
Emilie Kaufmann
Laura Richert
Venue: ICML 2025 poster (2025)
Keywords: pure exploration
bandit
theoretical analysis
active learning
Pareto set identification
multi-objective bandits
Primary area: theory->online_learning_and_bandits
TL;DR: We study the identification of the Pareto Set in multi-objective bandits under linear feasibility constraints.

Abstract: In this paper, we address the problem of identifying the Pareto Set under feasibility constraints in a multivariate bandit setting. Specifically, given a $K$-armed bandit with unknown means $\mu_1, \dots, \mu_K \in \mathbb{R}^d$, the goal is to identify the set of arms whose mean is not uniformly worse than that of another arm (i.e., not smaller for all objectives), while satisfying some known set of linear constraints, expressing, for example, some minimal performance on each objective. Our focus lies in fixed-confidence identification, for which we introduce an algorithm that significantly outperforms racing-like algorithms and the intuitive two-stage approach that first identifies feasible arms and then their Pareto Set. We further prove an information-theoretic lower bound on the sample complexity of any algorithm for constrained Pareto Set identification, showing that the sample complexity of our approach is near-optimal. Our theoretical results are supported by an extensive empirical evaluation on a series of benchmarks.

Constrained Pareto Set Identification with Bandit Feedback
Cyrille Kone Emilie Kaufmann Laura Richert²
Abstract
jective (or a marginal) e for which arm is in expectation preferable to k' (i.e. P > .&.). Each arm in the Pareto Set satisfies an optimal trade-off between different objec- tives in the sense that no other arm can improve over it for all objectives. This setting extends the well-studied Best Arm Identification framework (e.g., Even-Dar et al. (2006); Audibert & Bubeck (2010); Jamicson & Nowak (2014)) to problems where multiple metries need to be optimized si- multaneously with no clear preference.
In this paper, we address the problem of identi- fying the Pareto Set under feasibility constraints in a multivariate bandit setting. Specifically, given a K-armed bandit with unknown means Mr...../K E Rd the goal to identify the set of arms whose mean is not uniformly worse than that of another arm (i.e., not smaller for all objec- tives), while satisfying some known set of linear constraints, expressing, for example, some min- imal performance on each objective. Our focus lies in fixed-confidence identification, for which we introduce an algorithm that significantly out- performs meiin-like algorithms and the intuitive two-stage approach that first identifies feasible arms and then their Pareto Set. We further prove an anformation-theoretii lower bound on the sample complexity of any algorithm for con- strained Pareto Set identification, showing that the sample complexity of our approach is near- optimal. Our theoretical results are supported by extensive empirical evaluation on series of benchmarks.
PSI has diverse applications, including recommender sys- tems where multiple performance metrics are considered (Lin et al., 2019; Huang et al., 2019; Mehrotra et al., 2020), or hardware or software design optimization (Almer et al., 2011; Zuluaga et al., 2013), which frequently involves trade-offs between metrics such as energy consumption and performance. We are particularly interested in potential applications to clinical trials, in which multiple biological markers may be tracked to assess the efficacy of a treatment (Munro et al., 2021), or in which efficacy and safety may be jointly monitored (Jennison & Turnbull, 1993).
In the literature on PSI, no particular constraints are im- posed on the arms in the Pareto Set, allowing for situations where an arm may exhibit very low expected performance one objective but still be in the Pareto Set due to its good performance on another. This lack of constraints may be undesirable in practice. For instance, in clinical trials, it may be important to identify good candidate drugs hav- ing some minimal performance level on some indicator of efficacy (e.g., a minimal antibody response in the case of vaccine development) or avoiding exceeding some maxi- mal toxicity threshold (Mark C et al., 2013). Similarly, in multi-objeccive recommender systems or material design optimization, one might be interested in finding the Pareto Set of items that satisfy some minimal performance met- rics or dimensions constraints (Kumar et al., 2021; Afshari et al., 2019). Existing PSI algorithms are unable to han- dle such constraints. To fill this gap. we introduce a novel active testing problem termed constrained Pareto Set Iden- tification. In this setting, the learner is given polyhedron P = fx E Rd Az < b} describing solutions to a set of linear constraints with A E Rm.d and b E Rm (i.e., m linear constraints). Any arm & such that μ4 E P is called feasible. The goal of the learner is to identify the Pareto Set of the feasible arms.
1. Introduction
Pareto Set Identification (PSI) is fundamental active test- ing problem in which a learner sequentially queries sam- ples from multi-variate multi-armed bandit to identify as efficiently as possible the arms whose average re- turn satisfics optimal trade-offs among possibly compet- ing objectives (Zuluaga et al., 2013; Auer et al., 2016). In this framework, a K-armed bandit is denoted v (M,,..., px) ), where each arm vs is multi-variate distribu- tion with mean μı Rd and d > 1. Given bandit model with means μ = (Pi...., ), its Pareto Set is the set of arms & such that for any other arm k', there exists an ob-
Lille, Inria, CNRS, Centrale Lille, UMR 9198- CRIStAL, F-59000 Lille, France "Univ. Bordeaux, Inserm, Inria, BPH, U1219, Sistm, F-33000 Bordeaux, France. Correspondence to: Cyrille Kone Ecyrille.koner ir.iaf
Univ.
Proceedings of the 1nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Constrained Parcto Set Identification with Bandit Feedback
We study the constrained PSI problem in the fixed- confidence setting. In this framework, the learner is al- lowed an unrestricted exploration phase and aims to iden- tify the Pareto Set of the feasible arms with high confi- dence, while minimizing the expected length of the explo- ration phase, called the sample complexity.
provide a reason for rejecting any arm that does not belong to O Every arm outside of O should be classified as either infeasible (does not satisfy the constraints) or dominated by feasible arm. Note that for arms that are both infeasible and dominated, both explanations are valid.
While cPSI may be adequate for certain applications, e- cPSI becomes particularly relevant in scenarios like clini- cal trials, where the experimenter needs a clear justification for rejecting each arm. This need for explainability makes cPSI especially important, and as a result, developing an efficient algorithm for it will be our primary focus.
1.1. Setting
We denote by K the number of arms, T 1 the number of objectives, and [K] == {L..... ......,, } the set of arms. We let DD be a family of distributions in RRd. Given a multivariate bandit instance V/ == (z1..... .KK E DK, we denote the collection of its mean vectors by /a == (141,---, PKK) E IK where I C Rd and μ4= == Ex-r [X]. We shall use f to represent the distribution v. In the sequel DD will be either a set of subGaussian distributions' (for algorithms) or a para- metric set of multivariate Gaussian distribution (for which we will derive lower bounds).
We remark that similar '6-PAC-EXPLANATORR" identification of a feasible arm that maximizes some linear combination of the objectives.
& Scott (2019) studied framework for the
1.2. Contributions
A natural approach to constrained PSI consists in applying first algorithm for identifying the feasible set (e.g., the one of Katz-Samuels & Scott (2018)) and then applying an algorithm to identify the Pareto set of the arms that were returned as feasible by the previous algorithm (e.g.. that of Crepon et al. (2024)). We will see in Section 4 that such a naive two-staged approach can be arbitrary inefficient. This highlights the necessity to propose algorithms specifically tailored to constrained Pareto Set Identification, be it with or without the explainability component.
At each time k E [K] (based past observations) and observes outcome Xt T/K independent of past actions and ob- servations. With F, =
1, the agent chooses an arm
K,, k++1) the a- algebra representing the history collected up to time f, we let F = (F,, > }} be the natural filtration associated to the sequential process. An algorithm for a multi-objective pure exploration problem -that, general, aims at finding the answer some question about the means μ is made of (1) a sampling rule to choose k, that is predictable i.c k++1 is Fe-meauurable; (2) a recommendation rule R, that gives an F:-measurable guess of the answer and finally (3) a stopping rule that determines a time T to stop the data acquisition process, which is a stopping time w.r.t. to F. The output of the algorithm is the recommendation made upon stopping, Rg. Given some algorithm, we denote by P. the law of the stochastic process {ke, t e 1} and by [. the expectation under Pp, The subscript may be omitted when v is clear from the context.
Our contributions are the following. First, we present in Section 3 sample complexity lower bounds for both the cPSI and e-cPSI problems. For cPSI, leveraging gradient- ascent approach, we propose an algorithm matching the lower bound in the asymptotic regime in which the error t
probability goes to zero (see Algorithm 2 in Appendix B), with complexity that remains polynomial in the number of arms. Yet such an approach cannot be used for the more challenging e-cPSI and we devote the rest of our effort to proposing and analyzing an efficient algorithm for this set- ting. In Section 4, we present e-CAPE, an algorithm lever- aging upper and lower confidence bounds to efficiently bal- ance exploration between feasibility detection and Pareto Set Identification. We provide upper bound on its sam- ple complexity and prove that it can be arbitrarily smaller than that of the two-stage baseline discussed above, and can be near-optimal for some classes of instances. Finally, in Section 5 we validate our algorithms through an empirical evaluation on two real-world datasets from clinical trials. Additional experiments are provided in Appendix G.
In the particular pure-cxploratinn cus in the paper, the agent is given a convex polyhedron P = f-= E Rd| Ax < b} where A E Rmmxd is matrix, b IRm and m is the number of constraints. Given this polyhedron, we consider two learning tasks in this work.
problems that are our fo-
Constrained PSI (cPSI) The learner should identify O*, the Pareto Set of the arms that belong to P.
Constrained PSI with explainability (c-cPSI) The learner should identify O but in addition she is asked to
'Letting (XT) be a realization of arm i, it is marginally o-subGaussian if for all c d, VX E R, E[eA(X--FF) c 2dd and corm-o--subGaanee if V/2 E Rd such that || = 1, XTx is a. subGassss.....
Notation Given æ E Rd, let o denotes its c-th compo- : y E X' the distance
nent and dist(z, X²) == to X, for X c Rd. cl(P) denotes the clasure of P. int(P) its interior and ap = cl cl(())int (int(( vin(()), (P), the boundary of P.
2

---

Constrained Parcto Set Identification with Bandit Feedback
For a, b E R. (a)+ == max(a, 0), a b min(a, b) and b max(a, b). We use bold symbols for matrices. A glossary of notation is provided in Appendix A.
gradient-ascent algorithm of Ménard (2019) and proposed efficient procedure for computing the (super)gradient of the optimization problem. Still in the same confidence regime, Kone et al. (2024a) introduced an algorithm that re- lies on the posterior distribution to determine which arm to sample at each round and when to stop collecting new sam- ples. While these algorithms are optimal the asymptotic regime for multivariate Gaussian arms, they do not come with an explicit upper bound on their sample complexity for a fixed confidence level ö. Hence, their performance in the moderate confidence regime is still to be investigated However, their practical performance is appealing even for moderate values of 8 and subGaussian arms.
2. Related Work
Best Arm Identification (BAI) can be seen as a special case of PSI when d' 1. In recent years, significant attention has been given to developing asymptotically optimal algo- rithms for fixed-confidence BAI when the arms distribution comes from parametric family. These algorithms satisfy strong optimality guarantees on the sample complexity in the regime where the error probability 5 is small. Notable contributions to this line of work include (Garivier & Kauf- mann, 2016; Degenne& & Koolen, 2019; Wang et al., 2021; You et al., 2023). Another line of research has developed efficient BAI algorithms using upper and lower confidence bounds (K (Kalyanakrishnan et al., 2012; Jamieson & Nowak, 2014), whose sample complexity bounds are expressed in terms of sub-optimality gaps, but is not matching the exist- ing lower bound when ó goes to zero.
Notably, none of these works address the additional chal- lenge of handling constraints on the Pareto Set.
Feasibility detection in multi-objective bandit problems was studied by Katz-Samuels & Scott (2018); given a set of linear constraints materialized by polyhedron /' C I4 one should identify the set of arms whose means belong to P. A constrained BAI problem was further studied by Katz-Samuels & Scott (2019): given weight vector w E Rd, the learner should identify the arm that maxi- mizes w μuk among arms k belonging to P. While this approach assumes a known preference weighting, it funda- mentally differs from constrained PSI, where no such pref- erence vector w exists to rank the feasible arms. In situ- ations where there is no clear preference vector w, it may be desirable to find instead their Pareto Set. For example in early-stage vaceine research, several immune markers are of interest, and it is that stage not yet known which one(s) are the most relevant to protect against new diseases.
Extending these techniques to multi-varian bandits induces additional complexity due the lack of total ordering among arms. Recent work has successfully addressed these challenges by proposing efficient algorithms for PSI.
Zuluaga et al. (2013; 2016) studied PSI in the bandit set- ting and introduced an algorithm based on Gaussian Pro- cess regression techniques and confidence regions to adap- tively identify the Pareto Set while sequentially discarding sub-optimal arms (i.e., arms that are not in the Pareto Set). Auer et al. (2016) introduced the first (s, 8) PPC algorithm for PSI and proposed lower bound on the sample com- plexity of this problem. The authors identified problem- dependent complexity term (1)) that is written as a sum of inverse square "sub-optimality gaps" and which is the leading term of the sample complexity. Karagözlä al. (2024) further extended the algorithm of Auer et al. (2016) to bandit multi-objective optimization under any cone- induced pre-order. Kone et al. (2023) introduced gen- cralization of the LUCB algorithm Kkalyannkrisshan et al., 2012) for PSI and studied different relaxations of the prob- lem to address different use cases. The algorithms of Auer et al. (2016) and Kone et al. (2023) both identify the Pareto Set by collecting at most O (H) log(K log( ())(H(()))/)))) ()) samples. An extension of PSI in which each arm is charac- terized by observable features on which its mean depends linearly was further studied by Kone et al. (2024b).
Finally, while we consider in this work the identification of the Pareto Set under known constraints materialized by P, other works have studied the constrained regret mini- mization setting where the learner should pull arms with the largest mean (single-objective, see Lattimore & Szepesvári (2020)) or arms inside the Pareto Set (multi-objective, see Drugan & Nowe (2013)) while satisfying some constraints (Amani et al., 2019; Li et al., 2024).
3. On the Complexity of Constrained PSI
In this section, we present some performance lower bounds for cPSI and e-cPSI. To do so, we first introduce some def- initions to formalize the two objectives.
Given the polyhedron P and a bandit instance v E DK with means μ := sigk, we let F(4) == {i I bz E P} be the set of arms that respect the linear constraints, called the feasible set.
Crepon et al. (2024) proposed an algorithm with tight guar- antees in the asymptotic regime (i.c., when d - 0). Their algorithm is based on iteratively solving an optimization problem that characterizes the optimal problem-dependent sample complexity of PSI. The authors extended the online
For two arms i,j, arm i is dominated by j (i x or Pi Hb) if pb & ug holds for all e E [d. For S c [K]
3

---

Constrained Parcto Set Identification with Bandit Feedback
and a parameter À E IK, we let Par(S, X) be the Pareto Set of {Ae l E 5): the arms in S that not dominated by another arm in S for the bandit A. With this notation, the Pareto Set of the feasible arm that we seek to identify is denoted by O" (1) = Par(F(()), F(u), (e) and we further let SH) = {i E [K] 3j E F(P) such that μu; < N be the set of arms that are dominated by a feasible arm. To simplify the notation, when μl is clear from the context, we will sometimes write F, O" and SubOpt.
be correctly classified either in Sy or I,. Therefore, mul- tiple correct ways to partition [K] may exist, so multiple correct (Sr, L.). Given the polyhedron P we define the set of valid answers for (S,, I,) as
M(P. p4) = [(S,1) S SubOpt(w), c F())) S T 0 and SUT= (0*()))))
To ease the notation, we simply write M when P and μ are clear from the context. This is an example of pure ex- ploration problem with multiple correct answers, a frame- work studied by Degenne & Koolen (2019) in single objec- tive bandits. With the notation above, the constrained PSI problem with explainability can be formalized building 6-correct algorithm according to the following definition.
3.1. Constrained PSI without explainability (cPSI)
In ePSI, an algorithm with stopping time 7 simply outputs recommendation R, O, which is guess for O Definition 3.1. An algorithm is 8-correct for cPSI on DK if for any instance ve E 'DK, with means μ E IK (Pu(T 00, O + (2)) < 6.
Definition 3.3. An algorithm is ò-correct for e-cPSI on D if for any V E D. with means μ E IK it outputs par- tition I,, of [K] s.t. PL(T < oo and -(O O¹, (S.. I+) E M)) & 5.
We are interested in 8-correct algorithms with small sam- ple complexity E. [Tx]. Given an instance v. to identify the (unique) correct answer, an algorithm must be able to dif- ferentiate V with means şe from any other instance // with means À for which (²() f (A).. To state our lower bound for parametric models, we introduce Alt(O") to de- note the set of instances of I. with different optimal set i.., Alt(O") E E IK (*) + O"}.
Again, we are interested in 8-correct algorithms with small sample complexity [T]]. To introduce the lower bound, given (O, I) a partition of [K] we introduce the set of instances for which (O,S, T) is not a correct answer: Alt(S, I) = {>1 (S, & MM(P
Proposition 3.2. Let D be the class of multivariate normal with identity covariance and v E DK with means μ E (R4y.. For any 8-correct algorithm for cPSI on D with stopping time T, it holds that
Proposition 3.4. Letting D be the class of multivariate normal with identity covariance and v E D* with means μ E I= For any S-correct algorithm for e-cPSI on DK with stopping time T, it holds that
Eg17] > T ((L) log(1/(2.45)) where,
ET[T]
lim inf
TM(H) = min T(H, S, I), where (S,I)EM
(H))) = max
inf WESK )
1 Σ wx ml - Aall. (1)
Σ k
8-40
(1g(1
T(u, -== max inf WESK XEALT(S.))
Wk 2
|p
The proof of this result follows general recipe given by Garivier & Kaufmann (2016). Efficient algorithms designed to match similar bounds often rely on iterative saddle-point methods (Degenne et al., 2020) or online learning algorithms (Ménard, 2019; Wang et al., 2021). In any case, such algorithms require efficient solvers for the inner inf problem in (1), which is often a non-convex prob- lem. In Appendix B, we propose an algorithm for cPSI of this flavor, called Game-cPSI (Algorithm 2), that matches the lower bound when 5 is small. Moreover, we show that its computational cost is polynomial in the number of arms.
This asymptotic lower bound derives from a game-theoretic technique used in Degenne & Koolen (2019). For (S, 7) E M. T(p, S, I) quantifies the information- thhooeetc cost to identify (S, as a valid answer. The lower bound states that the minimal sample complexity of any 8-correct de- pends the easiest-to-identffyy answer. Even if μ was known, computing (M()) would be non-trivial as it in- volves solving the inner inf problem for each element of M which is of size 2n for n. > 1, and empty for n = O, with n = [SubOpt n F satisfying 0 < n < K 11
Degenne & Koolen (2019) proposed an optimal algorithm for similar single-objective bandit settings. However, their approach requires enumerating all possible answers at each step and solving the inner inf optimization (2) for each, making it computationally expensive. In our setting, this would require iterating over the power set of SubOptnFFs which can grow exponentially with K, making the ap- proach impractical for large-scale problems.
3.2. Constrained PSI with explainability (e-cPSI)
In the more demanding e-cPSI problem, an algorithm rec- ommends partition R2 = (Or, I7) such that
i) 0, = 0", i) S, C SubOpt and 1, C Fe
holds at stopping time r. Since some arms can be both in- feasible and dominated by a feasible arm, such arms could
4

---

Constrained Parcto Set Identification with Bandit Feedback
Instead, we present in the next section a computationally efficient algorithm for e-cPSI based on upper and lower confidence bounds. We will show that its sample complex- ity is close to optimal in some instances, and assess its good empirical performance.
Remark 4.1. When the arms are known have inddpen- dent marginals, we
du = On the other extreme, when nothing is known on the covariance structure, we can always set d. = vdo.
Pareto Set Estimation For each pair of arms (i,j), we build time-uniform confidence intervals around the un- known quantities j) and m).
4. A Near-Optimal Algorithm for e-cPSI
Following the APE approach for (unconstrained) PSI from Kone et al. (2023), we base our algorithms confidence regions on some quantities that allow to access whether an arm is dominated or not. For any pair of arms i,j, we in- troduce
Lemma 4.2. Under &t. for all i,j it holds: : (1) f)
M(i.j;;tl & B:(t) + B, (t) and lml(ū, - jit] <
(t) + (,(,), (ii) for any X R [dist(Re,,) X)
dist(p X)1 & U,(t).
This result justifies the introduction of the confidence bounds M (2, = M(i.j;;)) + (B:(1) + B,({)) and similarly m (2, = m(i.j:t) = (3,(t) + By))). such that m) E (i. (i.j:t) and Mii,) E
M(i,)) = max - [4]] m(i.j) = minluj- - -M1. (3)
esd
for which j( = - Note that J) > 0 if and only if 14; is not dominated by μj (ui A Hg). We also introduce quantities expressing the hardness of accessing the feasibility of each arm i (Katz-Samude & Scott, 2018):
[M (i, (1.): on the event E. In particular on that event, M (i. > 0 implics that H4; * Pj (arm is not dominated by j) and M (i,jit) < 0 implies that P4 < M4 (arm i is dominated by j).
(ist P) T/
if $ P. EP
(4)
dist Po)
Feasibility Detection For any arm introducing the quantity ni(1) = 2 Ne, (1) g(t, 6), one can show us- ing Lemma 4.2 that when (x()) > O, the vectors fus, and 1u; can either both belong to P or to Ps, with high confidence. We let G. == (i E Ff (t)) < 0} be the subset of Fţ of empirically infeasible arms that cannot be confidently ruled out as infeasible at time t.
4.1. Constrained Adaptive Pareto Exploration
Our algorithm, called constrained Adaptive Pareto Explo- ration with explainability (c-cAPE) assumes that the arms are subGaussian and relies on confidence bounds to effi ciently balance between feasibility detection and PSI. Its pseudo-code given Algorithm 1.
Stopping and Recommendation Rules An algorithm for e-cPSI should stop as soon as any confidently valid an- swer has been identified. To introduce the stopping rule, we first define zf (t) = minseo, (t()) and 2 = minggo, min [M] (i, We further define
At any round t, we let Nr,i denotes the number of pulls of arm i up time t, and fu., its empirical mean based on the Ne, samples collected. We let M(i,j: f), m(i, j: L) and (t) denote the empirical versions of the quantities introduced in (3) and (4) (i.e., evaluated for the empirical means ()) F; == {il fu.s E P] is the empirical feasible set and O = Par( Fr, (ae) the empirical Pareto Set of feasible arms with i.= := (Re,,) sEEK..
(t) min ( (t), 2))))
When 2f((t is positive, arms in On can be proved to be feasible, and having z (t) positive is sufficient to guar- antee that arms in O2 are not dominated by each other. Thus, when (t) > O, arms in O₂ are all confidently feasible and non-dominated by each other. However, this alone is not sufficient to ensure that O O We also define (t) == max [R) In (i. t) and note that (t) > 0 implies that there exists j * i E (Fe U G.) such that μ4; < utj. Therefore, 1,gF, ((Ta()) > 0 implies that either arm is infeasible or it is dominated by an arm of (F, U G,). We then introduce,
We introduce some high-probabilg events
& = (Vi E [K], ||ãe, - milbo < &Be(t, 8) and || milla < {)), = n &
f1
with confidence bonuses of the form
f(t and U)( =
20 5) N1,1
8,(t,))= =
No.1
Z2(1)== == min [S(()EEFF ((x(1) V ((0))
(6)
kE(K].o,
We assume that the functions f,g (to be specified later) guarantee that PE( > 1-5 when v is marginally σ- subGaussian and norm-o, Norm-o,-SuuGaane SubGaussia...
for which a positive value guarantees that each arm outside of O2 can be confidently classified as either infeasible or
5

---

The analysis of cAPE features a new complexity quantity, that we first present, Additionally to 7) which measures the Constrained Pareto Set Identification with Bandit Feedback
dominated by another arm of (Fr U Ge). We will prove that having both Z (t) > 0 and (t) > O for some is sufficient to prove that O2 = O and to identify correct answer (S,, I&) E .M. Thus, we define the stopping time r of our algorithm as
Algorithm 1 e-cAPE
Initialization pull each anm once for L = K + 1, K + 2.... do Compute F;, the empirical feasible set
Compute O2 = {i E F. Viljj Ar, A p&s)
(7) At stopping, the algorithm recommends the partition (O,, Sr, 17) of [K] with O = (ar (r),, S, = (F, U G,) a set of arms that will be shown be dominated by some arms in O,, and I, G. n Fç, set of arms deemed infeasible.
r = inf(t > 1 (t) > 0 and (t) > 0}.
if Z2(() < then
Get b = minimizer of (6)
else
Get = minimizer of (f) if (t) 21 else.
end if
Get C2 == argmin j M (b) if min (1), Z2(()) > 0 then
In Appendix C.I we formally prove the correctness of the proposed stopping and recommendation rule.
break and return (Ot, (F. F2 nG;) end if
Lemma 4.3. On the event E, if e-cAPE outputs (O,, Sr, 1.), we have O = 0 and (5,,1r) E M(P. (.).
Pull arms b, and ce end for
The above result holds regardless of the sampling rule that is used, but the sampling rule is crucial to stop early.
hardness of feasibility detection for arm i, depends on some complexity measures from the PSI literature. Given S C [K] non-empty set, the complexity of identifying Par(S, pt), the Pareto Set of S in the unconstrained setting is governed by some "sub-optimality" gaps (Auer et al., 2016; Kone et al., 2023): for an arm i Par(S.
Sampling Rule The challenge in designing an efficient sampling rule for constrained PSI lies in efficiently bal- ancing the information about feasibility and Pareto domi- nance. We propose a sampling rule in the spirit of the top- two algorithms for best arm identification, of which LUCB (Kalyanakrishman et al., 2012) can be viewed as the first in- stance. We define the leader b, greedily w.r.t the stopping rule, as follows:
= A = max m(i,j).
jEPar(S.
by = the minimizer in (6)
Z2 < O else.
which can be viewed as the smallest quantity that should be added component-wiss to μr to make i appear Pareto optimal w.r.t {uy lj S SY()) For an arm e Par(S. p)),
(8)
Intuitively, if the algorithm has not stopped, and (2) < O, there is an arm of Of for which the evidence collected is not enough for it to be confidently classified as infeasible or dominated by an arm of (F, G.) so this arm should be pulled again. Similarly, if (t) > and the algorithm has 0 so that the status of arm in O, is uncertain and this arm should be pulled. Then we
A,( = min mii))=ii(66?)) (in 6, (S)), where
(10)
(5) = min min (in, M(J. and
jcPar(S.))()
not stopped, then (t)
5, (S) == min [(M() A,),
jes Par(S.
define the challenger of the arm by as an arm that cannot yet be ruled out as infeasible and that is close to dominating be:
with ming +00. ,,- accounts for how much i is close to dominating (or to be dominated by) another Pareto-optimal arm of Par(S, 14) while 6, quantifies the smallest "margin" from an optimal arm i to the sub-optimal arms.
Ct == argmni M (b).
Pulling b, brings information about it being feasible or infeasible and further pulling e brings information on whether b, is dominated by another arm of (F)UG;) which as samples are collected will ultimately be the feasible set F. Sampling both b, and e should increase the stopping statistic Zt) min (t), Zz(t)).
To identify (S, E M as a correct answer, an algorithm should (i) identify the Pareto Set of (O*US), (ii) certify that arms in O are feasible and (iii) arms in I are not feasible. We introduce below the quantity to measure the complexity of validating this candidate answer:
202
20
Clv, ((v,8,1)==
Σ max
4.2. Sample Complexity Guarantees
Ai US)
11/
IEO
(11)
202
20
+ Σ iES
+ Σ
A? US)
m
NET
6

---

Constrained Parcto Set Identification with Bandit Feedback
Interestingly, our upper bound scales with the complexity of the easiest verify such answers:
the leading complexity term of e-cAPE is always smaller than that for the two-stage approach that first identifies the feasible set and then its Pareto Set. Compared to this base- line, e-cAPE does only pay for the "PSI cost" of arms in SubOpt n F, and for arms in SubOpt n F it pays the smallest cost between infeasibility and Pareto dominance.
C2(l))= = (S.I)M((PI))
min S,),
Theorem 4.4. Let f(t,5) = log( 4kt Akikdee" ot,
We present in Figure an example which the complex- ity of cAPE can be arbitrarily smaller than that of the naive two-stage approach.
log( 4ks K5"(" with 1n > ++ a-I and D the class of marginally o-subGaussian and ou fu-norn-subGausion rributions. Then for any a 2 and 5 E (0, 1), e-cAPE is ó correct on DKK Moreover, for all E DK with means E IK
5
dis-
(0,1),
[41 Kd) 1/a 5
2 X
[.] <128C*n()) log 64C2((0)
1/1
+
+ +4H(U,F F?) +a.
where H(u, FO)= = E'EPrUO
320² log(3//d) and
V/á
20-1 Aa <
[ dd) + f(T,
Figure 1: Example of an instance of constrained PSI. The com- plexity of a two-stage approach will scale with 1/1l + 2/s² + Σ ((1,2 while e-cAPE's complexity scales with 1/m + 3 Ei 1/A, when e < 1.
E (1)g(T)+1) T21
4k1
To-1
The proof of this result is given Appendix C.2. says that the sample complexity of cAPE essentially scales in C2((v) log( (CTz(0) in the regime of small values of 5. This is hard to compare in general to the lower bound of Proposition 3.4. However, we prove in Appendix E that the complexity of some particular instances has to scale with (V), which makes our algorithm near-optimal in worst-case sense.
Moreover, we remark that when the arms are very far from the boundaries of P, i.e., >> 1, e-cAPE matches the bounds of Auer et al. (2016) and Kone et al. (2023) for PSI on F. Similarly, when the PSI problem is easy (i.c., A, > 1) our guarantees are tight for feasibility detection.
Improved Confidence Bounds While we stated the guarantees of c-cAPE using specific confidence bounds of the form /log(t" /5)/Ne, (with a > 2), the correctness of e-cAPE can also be established under tighter bounds of the form v logloglog(NN..)tooo + Hlog 4] as prescribed by No.,
Theorem 4.5. There exists class of multivariate Gaus- sian bandit instances D such that any 8-correct algorithm for e-cPSI satisfies, for all v E DD with means μ E IK,
lim inf [v(Ta] 8-40 (1g()
CM(()
the law of the iterated logarithm (Jamieson et al., 2014; Kaufmann & Koolen, 2021). Although our techniques do not provide bounds on the expected stopping time under these tighter confidence intervals, we can, following the approach of Katz-Samuels & Scott (2019), show that an upper bound of the form
>
8
Moreover, since (FNO"",F F.) is always correct answer, we further observe that
(M(()) <C(u, F2)
Kdd To < O (Culie) log ( log (o((C(()))
20
20 v
20
20 "
Σ max
(F(
AF()
IE0'
V
OF
iFF
holds with probability at least 1 5.
20
20 U %
As highlighted in the experimental section, we advocate for the use of such tighter confidence bonuses, as they yield better empirical performance, even though they main conservative in terms of misidentification errors.
(F((F)
SEF
KE[K]
(rs((r)
H (v())
HF accounts for the complexity term for identifying the feasible set (Katz-Samuels & Scott, 2018) and Hpst is the leading complexity of identifying the Pareto Set of the fea- sible arms (Auer et al., 2016; Kone et al., 2023). Thus,
Furthermore, if each arm is assumed to be multivariate Gaussian with known covariance, applying the Hanson- Wright inequality for Gaussian vectors (Rudelson & Ver- shynin, 2013) allows us to achieve norm-2 concentration
7

---

Constrained Pareto Set Identification with Bandit Feedback
bounds that depend the trace and operator norm of the covariance matrix, rather than on exponential dependence in the dimension d, as is typically the case with cover- ing arguments over the unit sphere (Katz-Samuel & Scott, 2018).
reports average immune responses from COVID-19 vac- cine trial involving 20 strategies. Following Crepon et al. (2024), we focus on three indicators: neutralizing antibody titres (NTso), immunoglobulin G (IgG), and wild-type cel- lular response. The unconstrained Pareto Set includes two strategies, and the feasible region is defined by arms with IgG response above 8.25 titre. Figure shows the average responses and feasible region.
5. Experiments
We evaluate the performance of e-cAPE on two instances inspired by real-world data. We compare against the fol- lowing baselines:
5.2. Results
We report the distribution of the sample complexity in Fig- ure 4. For the experiment on covboost data, we excluded the Uniform sampling algorithm due to its excessively high sample complexity.
MD-APT+APE (A-A): the two-stage algorithm that combines the optimal algorithms of Katz-Samuch & Scott (2018) and Kone et al. (2023) to first identify the feasible set then its Pareto Set
Our experiments show that e-cAPE performs well in both tasks, achieving a lower sample complexity than its com- petitors. In the dose-finding simulation, the 75mg arm is both near the feasibility boundary and suboptimal com- pared to the 150mg arm, which meets the constraints. By focusing answers (or partitions) with minimal cost, e- CAPE can classify such arms as suboptimal, whereas (A- A), the two-stage algorithm, incurs an additional feasibil- ity verification cost, which is high in this example. This finding is consistent with Figure I, which highlights the sub-optimality of A-A when suboptimal arms lie near the boundary of the feasible region. Additionally, in Ap- pendix F and Appendix G.3, we provide both theoretical and empirical evidence of the sub-optimality of the racing algorithm R-CP.
Uniform (U): pull arms in a round-robin fashion until the stopping rule (7) is met
Racing algorithm (R-CP): an adaptation of the climination-based algorithm of Auer al. (2016) for PSI to the e-cPSI problem, described in Appendix F.
In the experiments, (A-A), (U), (R-P) and e-cPSI are in- stantiated with the same confidence bonuses. Follow- ing the literature, we use slightly smaller thresholds than those licensed by theory and use the standard 3, = /20 log (log(t))))/N,... Moreover, for the confidence bounds on M and m, instead of using individual confidence intervals, we use confidence intervals on pairs, as in the experiments of Auer et al. (2016) and Kone et al. (2023), and set Bigj = 3
Appendix G. includes additional experiments on synthetic datasets, and details about the computational complexity of e-cAPE, These experiments confirm the robustness of e-cAPE to different scenarios (e.g. more complex polyhe- dra). We also compare in Appendix G.2 e-cAPE with our proposed optimal algorithm for the simpler cPSI objective, Game-cPSI (Algorithm 2). This preliminary experiment suggests that even for cPSI, e-cAPE may also be a good practical solution.
We set the error parameter to 8 0.1 and we reported negligible empirical error.
5.1. Datasets
We consider two datasets generated from real-word data extracted from clinical trials. Additional experiments on synthetic data are included in Appendix G.
Secukinumab trial. We use historical data from the phase 2 trial of Mark C al. (2013), which evaluated the safety and efficacy of secukinumab for theumatoid arthritis (also used by Katz-Samuels & Scott (2019) for constrained BAI). The trial involved 247 patients randomized to dif- ferent doses (25mg, 75mg, 150mg, 300mg) and a placebo, with probabilities of efficacy and safety reported. Using av- erage endpoints, we simulate Bernoulli bandit, aiming to identify the Pareto Set of arms with safety above and non- toxicity above 40%. Figure 2 illustrates the feasible region and arm responses.
6. Conclusion and remarks
We introduced novel multi-objective bandit pure explo- ration problem, where the goal of the leaner is to identify the Pareto Set while adhering to a set of linear fcasibility constraints. We established the fundamental complexity of this problem by deriving an enfoommtiion-theorete lower bound on the sample complexity required for any 8-correct algorithm.
Our main contribution is e-cAPE, algorithm that achieves near-optimal sample complexity in the explain- able setting. We also propose an asymptotically optimal algorithm in the non-explainable case.
CovBoost 19 trial We simulate a constrained PSI ban- dit instance using data from Munro et al. (2021), which
8

---

Constrained Pareto Set Identification with Bandit Feedback
Oo
0.55
100g
Feasible Region
Prob. of con-toxicity
response
0.50
26mg
0.45
placebs
300mg
10c
3.5
0.40
0.35
7
NT
0.35
0.40
0145
0.50
0.56
10
11
Prob. of effectiveness
Figure 2: Average response each dosage level. The fcasible region defined by an effectiveness at least 40% and non-toxicity
Figure 3: Average response each vaccine. The fcasible region is defined by an 1gG response larger than 8.25 titre
25.00
References
43.90
Afshari, H., Hare, W. and Tesfamariam, S. Con- strained multi-objective optimization algorithms: Re- view and comparison with application in reinforced con- crete structures. Applied Soft Computing, 2019.
32
15.00
2100
13.000
11.00
0.APE
4.6
R.CP
e:cPPE
A-A
R.CP
Almer, O., Topham, N., and Franke, B. A learning- based approach to the automated design of mpsoc networks. In Proceedings of the 24th International Conference on Ar- chitecture of Computing Systems. Springer- Verrgrr 2011.
Figure 4: Empirical sample complexity averaged on 500 runs for the secukinumab trial (left) and the covboost trial (right).
Amani, S., Alizadeh, M., and Thrampoulidis, C. Linear stochastic bandits under safety constraints. In Advances in Neural Information Processing Systems, 2019.
Through our simulations from real-world and synthetic data, we demonstrate the superior empirical performance of e-cAPF, highlighting its efficiency for constrained Pareto Set Identification.
Audibert, J.-Y. and Bubeck, S. Best arm identification in mudti- bandits. In COLT 23th Conference on Learning Theory, 2010.
While work ensures constraint satisfaction in the fi- nal recommendation, exciting avenue for future research is to explore adaptive strategies that allow controlled con- straint violations during the learning phase. This is par- ticularly critical in applications like clinical trials, where carefully balaneing exploration with safety constraints can lead to faster and more ethical decision-making.
Auer, P., Chiang, C.-K., Ortner, R., and Drugan, M.-M. Pareto front identification from stochastic bandit feed- back. In Proceedings of the 19th International Con- ference on Artificial Intelligence and Statistics. PMLR, 2016.
Acknowledgements
Crepon, E., Garivier, A., and M Koolen, W. Sequential learning of the Pareto front for multi-objective bandits. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, Proceedings of Ma- chine Learning Research. PMLR, 2024.
Cyrille Kone is funded by an Inria/Inserm PhD grant. This work has been partially supported by the French National Research Agency (ANR) the framework the PEPR FOUNDRY project (ANR-23-PELA-0003)
De Rooij, S., Van Erven, T., Grünwald, P. D., and Koolen, W. M. Follow the leader you can, hedge if you must. J. Mach. Learn. Res., 2014.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences our work, none which we feel must specifically highlighted here.
Degenne, R. and Koolen, W. Pure exploration with multi- ple correct answers. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2019.

---

Constrained Pareto Set Identification with Bandit Feedback
Degenne, R., Ménard, P., Shang, X., and Valko, M. Gamifi- cation of pure exploration for linear bandits. In Interna- tional Conference on Machine Learning (ICML), 2020.
Katz-Samuels, and Scott, C. Feasible arm identification. In Proceedings of the 35th International Conference on Machine Learning. PMLR, 2018.
Drugan, M.-M. and Nowe, A. Designing multi-objective multi-armed bandits algorithms: A study. In The 2013 International Joint Conference on Neural Net- works (IJCNN), 2013.
Katz-Samuels, J. and Scott, C. Top feasible arm identi- fication. In Proceedings of the Eventy-Secone Interna- tional Conference on Artificial Intelligence and Statis- tics. PMLR, 2019.
Even-Dar, E., Mannor, S., and Mansour, Y. Action elimina- tion and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Ma- chine Learning Research, 2006.
Kaufmann, E. Analysis of bayesian and frequentist strate- gies for for sequential resource allocation. Thesis, Télécom ParisTech, 2014.
Kaufmann, E. and Koolen, W.-M. Mixture martingales revisited with applications to sequential tests and confi- dence intervals. Journal of Machine Learning Research, 2021.
Garivier, A. Informational confidence bounds for self- normalized averages and applications. In 2013 IEEE Information Theory Workshop (ITW). IEEE, September 2013. doi: 10.1 0..1009/tw.220136661111 URL http: //dx wtw.i.org/iii.. wtt.o//o//...11/1......... 2013. 1111666111......1.6611111.. 6691311.
Kaufmann, E.,, Cappé, O., and Garivier, A. On the com- plexity of best-arm identification in multi-armed bandit models. Journal of Machine Learning Research, 2016.
Garivier, A. and Kaufmann, E. Optimal best arm identifi- cation with fixed confidence. In 29th Annual Conference Learning Theory. PMLR, 2016.
Kone, C., Kaufmann, E., and Richert, L. Adaptive algo- rithms for relaxed pareto set identification. In Thirty- seventh Conference Neural Information Processing Systems, 2023.
Huang, Z., Liu, Q., Zhai, C., Yin, Y., Chen, E., Gao, W., and Hu, G. Exploring multi-objective exercise recom- mendations in online education systems. In Proceedings of the 28th ACM International Conference on Informa- tion and Knowledge Management. Association for Com- puting Machinery, 2019.
Kone, C., Jourdan, M., and Kaufmann, E. Pareto set iden- tification with posterior sampling. 2024a.
Kone, C., Kaufmann, E., and Richert, L. Bandit pareto set identification in multi-output linear model. In Seven- leenth European Workshop on Reinforcement Learning, 2024b.
Jamieson, K. and Nowak, R. Best-arm identification algo- rithms for multi- aamei bandits in the fixed confidence setting. In 2014 48th Annual Conference on Information Sciences and Systems (CISS), 2014.
Kumar, A., Wu, G., Ali, M. Z., Luo. Q.. Mallipeddi, R., Suganthan, P. N., and Das, S. A benchmark-suite of real-world constrained multi-objective optimization problems and some baseline results. Swarm and Evo- lutionary Computation, 2021.
Jamieson, K., Malloy, M., Nowak, R., and Bubeck, S. lil' ucb : An optimal exploration algorithm for multi- armed bandits. In Proceedings of The 27th Conference on Learning Theory. PMLR, 2014.
Lattimore, T. and Szepesvári, C. Bandit Algorithms. Cam- bridge University Press, 2020.
Jennison, C. and Turnbull, B. W. Group sequential tests for bivariate response: interim analyses of clinical trials with both efficacy and safety endpoints. Biometrics, 1993.
Li, D., Zhang, F., Liu, C., and Chen, Y. Constrained multi- objective bayesian optimization through optimistic con- straints estimation, 2024.
Kalyanakrishnan, S., Tewari, A., Auer, P., and Stone, P. PAC subset selection in stochastic multi-armed bandits. In Proceedings of the 29th International Coference on International Conference on Machine Learning. Omni- press, 2012.
Lin, X., Chen, H., Pei, C., Sun, F., Xiao, X., Sun, H., Zhang, Y., Ou, W., and Jiang, P. A pareto-efficient algo- rithm for multiple objective optimization e-commerce recommenting In Proceedings of the 13th ACM Con- ference on Recommender Systems, RecSys '19, Associ- ation for Computing Machinery, 2019.
Karagözlü, E. M., Yıldırm, Y. C., Ararat, C., and Tekin, C. Learning the Pareto set under incomplete preferences: Pure exploration in vector bandits. In Proceedings of The 27th International Conference on Artificial Intelli- gence and Statistics, Proceedings of Machine Learning Research, 2024.
Mark C, G., Patrick, D.,, Hanno B, R., Jerzy, S., Eva, D., Vadim, M., Jacob A, A., Sang-Heon L., Christine E, C. Herbert, K., Takashi, I., Sophie, H., and Shephard,
10

---

Constrained Pareto Set Identification with Bandit Feedback
M. Efficacy and safety of secukinumab in patients with rheumatoid arthritis: phase ii, dose-finding, double- blind, randomised, placebo controlled study, Annals of the rheumatic diseases, 2013.
Zuluaga, M., Krause, A., and Püschel, M. e-pal: An tive learning approach to the multi-objective optimiza- tion problem. Journal of Machine Learning Research, 2016.
Mchrotra, R., Xue, N., and Lalmas, M. Bandit based op- timization of multiple objectives music streaming platform. KDD '20. Association for Computing Machin- ery, 2020.
Ménard, P. Gradient ascent for active exploration in bandit problems, 2019.
Munro, A.P..-.., Janani, L., Cornelius, V., and et al. Safety and immunogenicity of seven COVID-19 vaceines as a third dose (booster) following two doses of ChAdOx1 nCov-19 BNT162b2 in the UK (COV-BOOST): blinded, multicentre, randomised, controlled, phase 2 trial. The Lancet, 2021.
Réda, C. Tirinzoni, A., and Degenne, Dealing with misspecification in fixed-confidence linear top- m identification. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 25489-25501. Curran Associates, Inc., 2021. URL oc cc pcrppappe_fLleeesppprr/////// dffc3339979aafdd1ccaa551-------9 pdf.
Rudelson, M. and Vershynin, R. Hanson-wright inequality and sub-gaussian concentration, 2013. URL https: //arxiv. www//rr//bb...oeoeoo.ee/..oeeeee 110113366020 2872.
Wang, P.-A., Tzeng, R.-C,, and Proutiere, A. Fast pure exploration via frank-wolfe. In Advances in Neural In- formation Processing Systems. Curran Associates, Inc., 2021.
Ye, Y. and Tse, E. An extension of karmarkar projec- tive algorithm for convex quadratic programming. Math. Program., 44(2):157-179, July 1989. ISSN 0025-5610. doi: 10.6007./ URL. https://doo 101..011000//0007000585
You, W., Qin, C., Wang, Z., and Yang, S. Information- directed selection for top-two algorithms. In Proceed- ings of Thirty Sixth Conference on Learning Theory, Pro- ceedings of Machine Learning Research. PMLR, 2023.
Zuluaga, M., Sergent, G., Krause, A., and Püschel, M. Ac- tive learning for multi-objective optimization. In Pro- ceedings of the 30th International Conference on Ma- chine Learning. PMLR, 2013.

---

Constrained Pareto Set Identification with Bandit Feedback
A. Outline and Notation
In Appendix B, we describe and analyze the complexity of an optimal algorithm for cPSI. The proof of the sample com- plexity of Algorithm 1 lies in Appendix C. Appendix D contains technical results used the proofs. A gap-based lower bound for e-cPSI proven Appendix In Appendix F analyze the limitations of a racing algorithm for e-cPSI. In Appendix G, additional experimental results provided for more complex polyhedra and instances with large number of arms. The experimental setup is also described in Appendix G for reproducibility.
Table 1: Notation for the setting.
v μ OP,int(P) F
Bandit model and its matrix mean parameters Polyhedron expressing the constraints {ar E Rd Ax < bj
Boundary and interior of the polyhedron Set of feasible arms {i 14 P) Pareto Set of the feasible arms Pareto Set of the vectors {A, l E S} Set of arms that are dominated by an arm of F Infeasible arms that are dominated by a feasible arm.
Or
Par(S, A) SubOpt
= SubOpt F
We recall some commonly used notation: the set of integers [K] == {1,.... ,K,, the complement X and inte- rior (X) and the closure cl(X) of set X, the indicator function 1x of an event, the probability P, and the ex- pectation IE, under distribution v. Landau's notation o, O, Q and θ, the (K 1)-dimensional probability simplex SK = {w W E RK 2 0, ΣiE[K] w, = 1]. For a, RRaab = min(a, b) and V b = max(a, b). We write i E F2 to when i P and & F, otherwise.
Table gathers problem-specifie notation, and Table groups notation for the algorithms.
Table 2: Notation for algorithms.
Stopping time of the algorithm
Sample mean of arm ls at time
Nr
Number of pulls of arm & to time /
Fi
Empirical feasible set at time t
O
Empirical Pareto Set of feasible arms at time t
B. An Asymptotically Optimal Algorithm for ePSI
In this section, we describe 8-correct algorithm tailored for the simpler cPSI problem (see Definition 3.1), which the algorithm should identify (H(H) without the need to provide classification for arms not in O"()). We give an upper bound on its sample complexity, establishing its asymptotic optimality. We further analyze its computational cost and show that it is polynomial in the number of arms.
B.I. A Game-Based algorithm for cPSI
We propose an algorithm for the constrained PSI problem. Our algorithm, Game-cPSI, is based game-theoretic interpretation of the lower bound. Indeed, argued in Degenne & Koolen (2019), T can be interpreted the value of two-player game between the algorithm which plays randomized strategies on the simplex and the nature selects the best alternative in Alt(O") to confuse the first player for identifying the optimal set O*. The pseudo-code of Game-cPSI is described in Algorithm 2.
Sampling Rule We adopt the two-player iterative saddle-point solving scheme recently popularized by Degenne & Koolen (2019). We maintain learner L.x on the (K - 1) dimensional simplex Sk. each round, the recommen-
12

---

Constrained Pareto Set Identification with Bandit Feedback
dation O is computed from the empirical means and compute
argmin A
Σ Wi,s 10,,s Aslle.
The mixed strategy We of the sup player is computed from La (for example using AdaHedge (De Rooij et al., 2014)) then the algorithm selects kę ~ wy and pulls arm kt. The learner Lsx is then updated with gr. an optimistic value the payoff, which we make explicit below.
Stopping Rule We GLRT (Generalized Likelihood Ratio Test) stopping rule. At each round, the GLRT statistic is computed, and the algorithm stops if this statistic exceeds threshold h(t, 6), i.e., if
Nos Σ N ΣE
inf (,,)
| 2112 > h)t,
and the algorithm recommends On at stopping. The threshold h(t, 8) is calibrated to ensure the correctness of the recom- mendation with high probability. In particular, the threshold designed to ensure that for any E (0, 1), the event
Ni 2
liçe, pal3 < h(tt hlt:,)) 8)
Vt
K,
holds with probability at least - 8. Introducing Ct == h(t? 1/t2) //N, we define
gr(w) = Σ w:llee de,il22 v(r,))
Using the property of the event Eş and triangular inequality, simple toe prove that this definition of gi guarantee optimism (i.e. ge(w) > Σ wi l )e, with probability larger than (1 1/f)).
Algorithm Game-cPSI
Initialize: pull each arm once, Wk-1 = (1/K,... 1/K) for /. = K, 2.... do
Let F; = {i Añ & b) the empirical feasible set Let O, = (i E F, Vjj E FM Ar, A }
if (O)(O)) Σ, N., Aull > h(t, 8) then
break and return O end if
Get w, from the learner Lsx
Get A = argminieAAtion E, We Aol3
Update LA with gains g-(-)
Get Ki ~ Wt
Pull h2 and collect observation X₁
t++1
end for
B.2. Theoretical guarantees
Lemma B.I. (Kaufmann Koolen, 2021) With the threshold h(t,5) = 2Kd log(t/(Kd))) + Kdeg log(1/8)
Kd
the GLRT stopping rule ensures that Pu(T < 00, # (+)) < 8, for any v E DK with means l E I and ca(x) x x +z)((x).
Theorem B.2. Let D the class of d-variate distributions with independent I-subGaussian marginals. For any D. with means μ E I Game-cPSt satisfies
EX[T8] TT*
limsup 8-0
1og(1/8)
13

---

Constrained Parcto Set Identification with Bandit Feedback
The proof of this theorem follows from classical recipes developed in (Réda et al., 2021; Degenne al., 2020). The specificity of our contribution is to come up with efficient implementation method. Therefore, focus describing the procedure for computing the "best response" X == argmin)eAAM(O)) E, (r,,ille, A:ll2. which is the most critical part in the implementation of Game-cPSI.
B.3. Computational cost
The main computational cost of Algorithm 2 is due to the computation of A In a recent work, Crepon et al. (2024) proposed an algorithm to compute the best response X in the case of unconstrained PSI (i.e., for A = 0, E R ) The
+ d d d-1
where is the size of the Pareto Set. We will show that their algorithm can be adapted to the case of constrained PSI. We prove the following result, which allows us decompose Alt into two simpler sets Alt (O) and Alt (O).
computational cost of their algorithm is O (k(p+ + d) d)
Lemma B.3. It holds that
Alt(O) = (0) U Alt (O)+ where
(O) = U (IA A ( X & 111)
I,EO
All+(O) (0) = UiAETK &b E C, & 1,)
140
Proof. We have
X E Alt(O)
= O'(2) #0
(o):310))0(()) or (b) :i & O such that E (A))
0 s.t. X & Por A < X, or (b) Ei & O.t. X e and E O,
To see the direct inclusion, let X E Al) If & F(A) then (a) follows. Next, we assume O F(A).
As O # Alt(O), either (A) + 0 or 0 (*A)(O + 0. Assume there exists i E such that & (*)).
If A & P. then, as in the case above, the inclusion follows. Assume X; E i.e., i is still feasible arm in X. this case, there exists (A) such that Xj. otherwise, we would have i (A).
If j O, then the inclusion (a) follows. If & O, then, j (*))), we have by E P and Ak E F(A), A A d In particular, as O C F(A) it holds that for & E O: Ny A d and j E (A) C F(A), so (b) follows.
Now we assume there exists i E (A) such that i & O, as we have i E (*)) it holds that X; E P and Vj E F(A), A Ay. in particular, as O c F()), we have Vj E O, A Ay, then (b) follows.
For the reverse inclusion, assume (a) holds. Then, it follows directly that we cannot have 0 = (A). Similarly, suppose A.e. i.e., i is feasible (b) holds and O O² (A). Then 7i c O O*(A) such that i F(A) and Vj 6 (*)),, A Aj
in the instance X, it does not belong to the optimal set O (A) and it is not dominated by any arm of O O*(A), which is impossible if O= = O" (A). Therefore, when (a) or (b) holds, we have À E Alt(O).
Lemma B.4. It holds that
inf Ej willas x min(á1. 62) where AEAlt (0) 1
1
Φ1 min wi dist(p,, 2 IEO W,W,
22
min ME
24))
wi + w cgd
and minimizer can be computed in time Opp2d + pdm) where m the number of constraints and p =O].
14

---

Constrained Pareto Set Identification with Bandit Feedback
Proof. We have
Alt Alt((o) U
U
U Ars
LIE
with
P. (NEIK &
Mij = (AEIK x
Therefore, letting (A) = E, wwillms A we have
inf - (0)
(w) = min inf Dw iEO ACT,
min inf Du(2)) I,EEO (#) AEAL
Next, we observe that
inf (A) = 2th dist(4 po)2 xEr.
and minimizer of this quantity can be computed in ((nd). Indeed, since μui (as E O), dist(ui, PS) = dist(ug aP), and the latter be computed in ((md) for polyhedron with matrix of constraints A Rm. (ef Lemma H.1 of Katz- Samuels & Scott (2018)). Finally Lemma 2 of Crepon et al. (2024) shows that the value of infxeA,, Dwo(A) and its minimizer can be computed in time O()'d).
Lemma B.S. There exists an algorithm that computes the value and a minimizer of inf xeAlt (0) E, 2 - Xill in polynomial time.
Proof. In the instances of A E Alt+ novel arm is added to the Pareto Set of feasible arms. From its definition in Lemma B.3, we have
Alt+(0) U Alt((o)
iEO%
where
Alt (0)= (XE E& P Aj E O, * A,}.
Then, note that to guarantee that arm is not dominated by j while minimizing the transportation cost, it is sufficient to move the arm (or both arms) along one objective. Therefore, to minimize the transportation cost D(w, A), it is sufficient to move arm novel point À E Rd (satisfying the constraints) and move each arm O only along the coordinate with minimal cost to make À not dominated by the (Ay)1e0. This amounts to solving the following optimization problem:
inf D(w, A) = inf 7 AEAlE((O)
wull - 21l + Σ 2w min(p} 2 JEO
(12)
AcRd
cgd
AAgb
The rightmost problem is related to the optimization problem studied by Crepon et al. (2024), except that now we have additional linear constraints AA < due to the constrained PSI setting. However, we will show that their algorithm can still be adapted to efficiently solve (12). To see this, we let e be a mapping from O [d] and introduce hş Rd - R4, defined as
b ol x.
(A) = 2 uy |ps 21l
JEO
Then remark that the optimization problem in Equation 12 rewrites as
min inf h (A) dE(d] Aeed AAge
(13)
where the notation [d] denotes the set of mapping from O to [d] and 10). However, shown by Crepon et al. (2024), not all such maps are valid, and there is no need to optimize hg for an invalid map. The authors proposed an
15

---

Constrained Pareto Set Identification with Bandit Feedback
efficient graph-based algorithm enumerate all the valid maps. They showed that the number of valid maps is bounded by p+d (++d1) Now, it remains to minimize he under the linear constraints for each valid map. Note that up to d-1
reordering of the quantities, ) in is piecewise quadratic, and the problem can be decomposed into at most pd convex quadratic problems with constraints Áv & b where A E IRm and IR*++2d is known that solving a convex QP can be done in polynomial time (Ye & Tse, 1989). Thus, when the number of arms is large and is small, the overall complexity of problem 13 is s(p25smm d, d.), where s(m 2d, d) is the time complexity of convex QP with m + 2d constraints in dimension d.
C. Analysis of e-cAPE
In this section, we show the correctness of e-cAPE and upper bound its expected stopping time, showing near-optimal sample complexity.
C.1. Proof of the correctness
Before proving the correctness of c-cAPE, we introduce some notation. We recall that is the polyhedron of feasible arms, the set of indices of the feasible arms and
0' = {il μa E P and Vj s. E P.p. A p5}
is the Pareto-optimal feasible set: SubOpt == {i [K] 3j E O' A < /ッ} which can be rewritten as
SubOpt == {i E [K] 3j E F\ < 131}
(14)
To this, note that if s4 μy and j F, then, as F, either j 0' or there exists j' O" such that My * My and so Ni < pg. Thus
3j E 15 #4 = 3j E (*) Mh < 15
(15)
and the reverse inclusion is trivial, which justifies (14). Finally, it is simple to check that for the polyhedron P.
dist(p, PT) dist(u, aP) V P.
(16)
Lemma C.1. On the event E, when cAPE stops and returns a partition (O,, I,, ), is a valid partition.
Proof. To show the correctness, we have to prove that the returned partition (O,, It) at = satisfies O2 0", C SubOpt and I, C Fe, In this proof, we assume & holds and we let =T T.
Step 1: Proving that S, C SubOpt. Following (15), we have to show that
Vi E Sj E F such that μ4 Ml.
(17)
By design, S. (F, (,) and stopping
]
Zz(t) = min
LieR
max (E(PLUG))M
m (i.jitt) + 1.eF, (ii(t) v max m (T..jtt) JE(F.UG.)M
iE[K]{O.
satisfics Zz(t)= > 0 so that
( max m (1.j:t) (E(PLUG))(() Vi E St, 1.F
+ Digf, (na(t) v
max m (1.5:t)) > 0. JE(ALG.)M
(18)
Remark that if E S, GG, then i & F, and (1(1) < 0 so by (18),
max m m (i,jit) 2 0.
JE(FLGJMM)
16

---

Constrained Parcto Set Identification with Bandit Feedback
which also holds if Fe. Thus, it holds that
Vi E St, max m (1.3;1) > JE(F.UG.)\())
(19)
which on the event E, using Lemma 4.2 and by the definition of m(i,j) yields
Vi E St. Aj E (F, U G.) such that - Kg-
(20)
However, this does not directly imply (17) as the stopping rule only guarantees that O2 C F and at this point, some arms in (Fr U Gr) could be infeasible (for the actual means). Thus, we shall prove that (20) holds for some j E Oz. Remark that by their definition, we have F, G2 = S, U U,. Let
He = Par(S:. u) = Ei Se IVj SMM A Anp
the Pareto Set of St based on the true means.
As He C. St, (20) applies and
E H₁ Rj Fi, (F.UG.) (S. UO,) such that μ4 < M4j
then, as H2 is the Pareto Set of St, arms in H₃ cannot be dominated by another arm of S.. Then, the equation above implies
Ei H4 Dj úijj Og such that 14 Fg
which as O2 yields
E H, Aj F)() such that μ4 < Fj-
(21)
Now, for i S He, there exists (by definition of H,). j E H, such that μ < My and by (21) there exists j2 e F such that My < Uja μ4 Mjz- Put together, have proved that
E St, Aj FXf such that #4 < Pj:
hence S, C SubOpt.
Step 2: Proving that J, C F.. The proof of this claim simply follows from the definition of 7, and Lemma 4.2. Indeed,
as 4 = G Pr C Of and by definition of Ge, it holds that for all arm i E 4, ((t) > 0. Then by definition of %. the previous yields (t) > 200
5t, and since i E Fe we invoke Lemma 4.2, and
M..
dist(yi, P) > dist P) - U.(1,)) = (1))) - U.(1, 6) > 0,
so $ P that is E F which achieves to prove that J, C F
Step Proving that O, = O First, note that (O,, St It) is a partition of [K) Since we have proved that S, SubOpt and 1, FS, and by definition O (SubOpp U FF) 0. thus it holds that O O
Then, noting that as (t) >> 0. proceeding similarly to Step 2, we have O C F, at this step it holds that
0 c 0, and O, F.
(22)
Moreover, from (t) > 0. we derive
ViO Vj (MM)) M(i,)) M M (1.jit) 2 0
which from the definition of M(i.j) translates
Wi WEO, O.O0))) p3-
(23)
17

---

Constrained Pareto Set Identification with Bandit Feedback
Therefore, as O Oc (22), we have
E E O,, Vj E EO'MO 14
which implies (using the transitivity of the Pareto dominance and the fact that any sub-optimal element in F is dominated by an element in O*) that
Vi E O₁, Vj E Fu Ag.
Moreover O2 C F, so Or C Ot hence the conclusion follows as O, = O"
Putting everything together, we have shown that the recommendation is a valid partition of [K], which concludes the proof of the correctness of Algorithm for e-cPSI (which also implies correctness of ePST).
Remark C.2. The proof of the correctness can be adapted to generic time-uniform confidence bounds on M ._m , using an event & = E && where
& = (A) > ((. E M(i,) E (M (1,,; ((.3:))). (1,5;)) m (m.
and
= (V) > 1, Vi E [K], n E (n) (0, (1))
such that & holds with probability at least - 8.
C.2. Stopping time and sample complexity
We upper bound the expected stopping time of algorithm 1. We recall that P is fixed and known to the algorithm,
M(P,p) = ((S,1) S SubOpt, c F and S SUI (0*)*
is the of correct answers. The idea of the proof is to show that if the algorithm has stopped after round and E, holds, then at least one of b,, c has not been sufficiently pulled w.r.t the cost of identifying any correct response of M. More precisely, we introduce the sets
(S(S) = -iE O" A:(0" US) & 48:(tt or 2U,(t, W?(T) = (iET: & (t),
(24)
(25)
W2(S) = (iES: A,(0 US) & (3)
(26)
We may omit the dependency in t when it is clear from the context. At round 1, any arm that belongs to W,(S, I) is called under-explored w.r.t (S, 1). In the sequel, as O fixed and uniquely determined, we simplify notation: given S c SubOpt, we write (5) to denote A U O*).
and finally, Wi(S = W
Proposition C.3. If Algorithm has not stopped at time and &, holds then for all (S, I) E M, (be,ee) W,(S,T) non-empty.
C.2.1. PROOF OF PROPOSITION C.3
In the remaining of this proof, we fix correct answer (S E M and we show that if the algorithm has not stopped at time I and & holds then one of b,, is under-explored i.e {br, et (sW, 7) & 0. First, we address the case (FrUG, (b+) = 0. Note that (F(UG)))( = 0, implies that arms in [K]((b)] can all be classified as confidently infeasible at round t. Then,
{br}
b, O else.
o" =
0
In both cases, the gap b, involves the quantity T62-- Assume E F, then b O
18

---

Constrained Pareto Set Identification with Bandit Feedback
Case 1.a by Fe then, as G. = and Fe U U. {br). we have
(2(
min ie(K]]0
LiEF
( (E((FUUGMM))
== (6.5:)) 1.e (x(()V V In
max In ((,66:)) } JE(FLUG)) max m ((.hittt)
min ipb
1.EF.
max (E(F
m((ii:t)) Ligh, (nl())
(E(FLUG.))(()
min ip
LigF
(i(())
max ME(ALGG)M
(1..:1))) (since =;= (b:})
0
which follows by definition of Gr: as G2 = 0 and P. (b.) So if the algorithm has not stopped, (1()) < 0. In this case, as O₂ is a singleton, we simply have
(t) = no, (t) <
(the reader can check the formula of (t) as F; = }br}. we recall minø = -0). 7b. (f) < 0 then implies m)(t) < U,(t,
Next, assume b, E F, then b, E O and
& x dist(uu. Po)
dist(pe Po) + Un, (1,
nh,
mx(t) + Ub, (t, 20, (t,
where the first inequality follows from Lemma 4.2. Thus, if be F we have by E (S). Now we assume b, & F. We observe that
Th. = dist(Hub, P) & dist(fr. P)+ (t,8)
0+ U1 (t,
which follows as by assumption b, E Fr. So we have be E W2(().
Case 1.b by E G2, then by definition no, (t) = dist(Ae.; P) - Uz(t, 8) & 0. By Lemma 4.2, either by & F and
nh = dist(Hub, P)
dist(pe,p. P) + Ub, (t, 2t,
or 6, E (so O" +{b,)) and
Th. dist Po) E dist(fur.er Po) + Un (1,
0 Un, (1, 8).
Therefore, either by & F and b. (T( or F [br} 0* and b (S). This concludes the analysis for the case (FU U.) {bt}.
In the sequel, we assume at round 6, (Fr U (bb) + 0. For this proof, we treat different cases for b,, in a series of lemmas summarized in the Table which covers all the possible cases that could happen regarding bt, Ct-
Case
Reference
by S, and e E O" b, O" and o O b Iorc, I GES
Lemma C.7
Lemma C.6
Lemma C.4
Lemma C.5
Table 3: References the exhaustive list of cases analyzed
The following lemmas are proved under the condition that cAPE has not stopped and &, holds.
19

---

Constrained Parcto Set Identification with Bandit Feedback
Lemma C.A. If the cAPE has not stopped and be or oe I then one of them satisfies d 2U,(1,)), ie. ()( (be, + V.
Proof. By design of b it holds that
dist(pr P) & Ui(t,)).
(27)
To see this, observe that if (2( < O, then, as in this case
by == argmin iEO,
(x(1) A min M (1,))0)
JEO:
and O, C F3 we have Pe,b, E P. so (27) trivially holds. If otherwise Z2(t) > 0 and Z1 < 0 then, recalling that in this case
( ( max m (1..tt) + lier. (t(() V (E(ELUGG)M
max m (i, (1,j:t)) )] JE(FLUG)))1
b argmin LIER sE[K]VO,
it holds that either i) b, E F. Pr, P and (27) holds or ii) b, F, and na. (t) 0 (otherwise (2(t) would be non-negative). which by definition of nb (t) yields Equation (27).
Next, if by E I, then, as the event & holds, Lemma 4.2 yields
no. = dist(pb, P) < dist(pr,b, P) + Ub. (t.
and combining with (27) yields no & 20b (t). Assume instead
I. In this case, as C E Fi U G. we either have dist(/r.c,, P) = O (when e E Ft) or 7b, (t) & (when & E G. C F2) ie dist P) & Ub, (t, 8) so that (27) holds.
Thus, the proof follows as in the previous case, leading to the conclusion that
na < 20, 8),
and so W?(T) n (bc, a # 0.
b,, c2 is under-explored. Lemma C.5. If cPE has not stopped and 0 E S then one bt,
Proof. c, E S C SubOpt, then there exists of E O such that
(c, = m(c,,
As of E F, it is easy to see that, on the event &,, of can not be declared as confidently infeasible at time f, so E Fe GG.
# ez then by definition of
C₁ argmax mn (be.jit)
JE(FLUG.)(())
it holds that m+ (bi, c55) > mn mbe, etst), which by definition of m mi, (i,j:t) yields
Ic [d] Pi,c, - -i. + (t, + (t. > pi - As. + Br. (t,)) + 3og (t
thus when & holds this implies that
Ice [d] mb= pl, < (t,
which in turn, implies
A, (S, 1) < 23,,, 5).
(28)
If otherwise by = eg E O* then as the algorithm has not stopped, either (t) < or (t) < holds. We analyze both cases below.
Case 1: (t) < O. In this case, as by design b, E Oç, either
a) b, E F3 and there exists j O, such that fr... f..j. that is by is empirically feasible sub-optimal or b) b, E F, holds.
20

---

Constrained Parcto Set Identification with Bandit Feedback
In the a), for the arm Os, as PL.b. Pe.j it holds that M(be,jil) & S M (br,ji0) 0. So, as j GG) and by definition of et it holds that M (bi,
MTb,, (x; & Oie
M(b, cx & Po, (t,8) + Re, 6),
(29)
then, note that as b, cj A6, & A., (S) (this follows from (10))
max (S), (S))
4e, (5) = m(ce; cj) -((..b)))
133 M
M(b,, Gt)
M(b,, Ct () + Sb, (1,6) + Br, (1, 2(3 (1, + 8c, (1, 5))
where (i) follows from Lemma 4.2, Thus, for ae, the least explored among by ct. holds that
(S) & 4Ba (t,
which implies that ar E 1) in the case a). In the sub-case b), we have be $ Fr, as by = o O we have
(ist, Po) < ( po) + Ub, (1, (by Lemma 4.2 on E,)
Ur (t,o), 8),
b. E W.(S, I) and this concludes the analysis of Case 1.
Case 2: (t) < 0 and Zz(t) > O. In this case, by design, be Oz. As
(t) min ((t)) A min jeoA((1)
[ [M (i.
negative, and b, is its minimizer, either a): there exists j E O, such that M MT (be,5; & which further yields
M (b, t) <
or b): 76, (f) < O. In the case a). proceeding similarly to Case L.a) will lead to the conclusion that ae, the least explored arm among b,, belongs to I), The latter sub-case b) leads to dist(fe,s, P*) < Ub, (t, 6) so, as b ct E O again we have
dist(Pu, Pc) (ir,b, po) + Un, (1, (by Lemma 4.2 on Ex) (1,
Tbe
that is b, Wr(S, I). Therefore, we conclude that one of b, e is under-explored.
Lemma C.6. be e O and at e O", then one of them is under-explored.
Proof. Note that in this case, by definition of the gaps (ef (10) and (4.2)), as be, Gt O",
As. (S) & M(b,, ci) and D., (S) & M(b...).
(30)
We analyze first the case Zi(1) 0, (t) > 0. By design,
by argmin 1EO.
((t))) A min M (i. JEOA((s)
so, (1) < 0, either by is not confidently feasible (i.e 76, (1) & 0 in which case the proof is similar to Lemma C.4) or there exists E O, (b,} such that M (br,j;t) < O. Which as j E F, (since O C. F)) and by design
C argmin
[M (b,(b,;;:().
JE(PUGG
21

---

Constrained Pareto Set Identification with Bandit Feedback
it follows that
M Cz3 & O.
(31)
Then, using concentration properties of () (cf Lemma 4.2) and from (30), it follows
max(Ab. Aa))
< M (b,, ct,
< M(b,, citt + Pb, (t, + (t,
2(5b, (t, 8) + 3c, (t)
where the last inequality follows from M (b,,, azt) & 0. For ar the least-explored among be, Ct. the latter inequality implies
A.. (S) < 48a, (1,
that is ar E W5(S, I), which concludes our proof in the case (t) < 0, (2 > O.
In the case (2) 0, recall that
( max m (1.J:t) + ligt. (i((t) V (EECR-G.)M
((.5:()
b. = argmin iE[K]VO,
1iEF
max m jE(FUGGMM
Assume b, & F; (i.e. be,,b, P). Then by design, since (t) 0 we have no (t) 0 and using concentration properties of Lemma 4.2, and as by E 0"
yb.
dist( PC)
< dist(pu,,.: Po) + (t,(t,)), Lemma 4.2 on &
Ub, (1,
which follows as Rr,b E ps, Thus b, W,(S, If be E Fi (i.e. Pr,b, E P), as by design b, E Of, then by Of n Fi so b, is empirically feasible sub-optimal and
Aj E O₂ such that je, Pr.j
that is there exists Aj& E (b,()) such that M(b;,;; t) & O, which as M MT (bc.j5 & M(be,j:t) for all j yields
3j E Fb such that M (br,
(32)
Therefore, by design of cz.
M M (b;, < 0
(33)
so that we have with (30),
max(Ax,()), (S)) (S)
(b,,,, ct,
M(br, ccit) + Bo (t, + Be, (t,
(t, + (t,
so, for a, the least explored arm among b,, Ct.
Do, (S) & 4,3,, (t, 8)
that is a E W.(S, T).
Lemma C.7. Ifb, E S and 6 E O* then either by or e2 is under explored.
Proof. If Zz) < then by design, as
1.EF ( (ELFUUGNM
(i.j::) ]]
b. argmin =EOKO,O
m (1.5:11) + 1.eF
(7e(()
max
JE(FUGG)))
22

---

Constrained Parcto Set Identification with Bandit Feedback
and
LiEF. ( max m (b.jit) + dier, (i(t)) V (E(FLUG)))(1
max m (6.2:t)) JE(F,
Zz(t) == min iE|K](O:
plus at E (b),)) we have m (be, (x:t) & 0. We invoke concentration properties on & to have
Ab, (S) m(4. b7) & (bb.b.b
where by argmax m(b j) and note that on the event E,, it holds that of (Fi U Gt) by definition of cz. m=bb, (br, trit) and replacing by its expression, further get
Db, & m*
A (S) < 2(0,, (1, + Bc, (1,
On the other side, observe that by definition of the gaps and as b, E S,
Aq (S) & M(b,, +)) + Ab, (S)
(34)
which then yields
Ae,(S) < (-m(bi cat) + (t, (t, + (t, m + c;: + Bo,, (t, 8) + Pe, (t,,
3o, (t, + (t.6)
(t,
(t,
thus
(s, & 2(3b, (t, (t, and (S) < 2(6,, (1, + (t,
so we conclude in the case (z) < 0.
Now, we assume Zz(t)= 0; then Z1 (t) (otherwise, the algorithm would have stopped). We still have
Ao. (S) m(br, b5) m (be, b): < m mb.. (ett)
m then, the idea is to show that m (b,, Cr2 1) < O. We will prove that for any (F, G. (b,, & 0. To see this, first, note that, as E O₂, for any E Fe, Pe,b, A fe.ss thus for any i Fe, (b,,, <
Now let i Gt. By Lemma C.8, there exists E Oz such that ju, < pt..
Having b - fe, would yield either jus - De.i + Pr.b, (if = be) by transitivity
Be,b < Pr.j
with j + be which not possible for j E O₁. Therefore, for any E Ft, m(be, & O, so combined with the previous display,
Vi (F) mb,, i; < 0. In particular, m(be, (x))) & Moreover, recalling that on &,, As, (S) & m (b, cit), we have (5) < (t. (t. Pa. (t. On the other side, as in (34), (S) M(b,, c.)+ Ao, (S),
therefore,
(S) < (- m(b, 0i + (1, + 3c, (1,))) + ((bb,,55) + 36, + Bag (1,8)
2(3 (1 (t,
Put together, we have proved that
A. (S) < Br, (1, 5) + Be, (1,0) and A,, (S) < 2(3 (1,5) + (l,
which again allows to conclude as letting the least explored among b, and
Du, 4Ba, (t,
that is a E W.(S,T) 7)
23

---

Constrained Parcto Set Identification with Bandit Feedback
Lemma C.8. Zl) > then, for any E Gt. there exists j Og such that Pi, Pr.5"
Proof. Recall that arms in G2 cannot yet be confidently classified as feasible or infeasible. As Zz(t) and G2 Og, from the definition of (2))), it holds that
max JE(PLLG)M))
m (f,j;() 0,
so there exists j j E (Fi (G) such that m (1.j:t > O, in particular, Pa, < Prg. Introducing
J= (J Pes < pr.),
will show that Jr * 0. Let S4 = (j (Fi GDM+) fr, < P and define H, Parl2, Pr. the Pareto Set of 94 based on the empirical means. By the result above, 52 is non-empty, H, is also non-empty.
We claim that H, C Fr. Indeed, for l E H. n Fy we have k G. n Of, then, as Z2(() > O, justified above for i, there exists 1 E (1) U G.) such that Pe,k < Ae,, however, as k E H2 = ParΩ,, Puz the above is only possible if 1 $ Ωg Recalling that I E (F, U (k) and + be we have I E (Fr U G.G so putting the above displays together, if H2 n F.. + 0, there exists and & such that
Du. - Pe, Pi, - fr.
but i A ir,, which is possible Pareto dominance is transitive. Therefore, H, F2 and since He + 0, Di 0. Thus, there exists E Fi (6 such that Rr,s < Pr.. Then, either O₂ or there exists j2 E O2 such that, Pe, < Pt.d2 In any case, there exists ja E Og (either or j2) such that fra,s X Pt.js.
C.2.2. PROOF OF THEOREM 4.4
We recall the theorem below.
Theorem 4.4. Let f(t, = log( 4k, Kdtt Kdt o-subGaussian and ---nnorm-suGGausseee Moreover, for all v E DD with means μ. E IK,
à (tg 6) = log( 4k,K541" with by > 1 a-1 and 'D the class of marginally
1
8 distributions. Then for any and 8 (0, 1). e-cAPE is 8 correct D
4hh [4h] Kd 1/a
[r <128C log 64CM(()
(
+ 4H(U,F") Aa,
where H(u, Fc) E.ereuo
320 log(s" /d)
and
1/
((TT,--d)) + ((T,1)
Aa
(log(T) +1)
4k
7a-1
7
Proof. Let T) E E be fixed. Let > 0 be fixed and observe that
T
T
min(Ts (T. T)
<
(1x7))))
2
t=
Then, assuming
CT
&
(35)
TT/2/g/E7
24

---

Constrained Pareto Set Identification with Bandit Feedback
holds, and using Proposition C.3 have
T
min(T8. T)
+
((27))
2
[T/2]
T
T
+
Σ
1 ((LEW((51//)eew(((55))
[=[T/2]
T
T
Σ
2
[T/2]
a=1
K
T
T
[T/2]
then, decompose the latter sum into three terms by defining the function R for U C [K] as
K
T
R(U) = Σ
aEU t= [T/2
have for the set SubOpt, using the definition (S) for S:
T
R(S)
Σ
Σ
aES
[T/22]
Σ
aES [T/2]
Σ
Σ
1 (0.
(as f is increasing)
OES [=[1/2]
therefore,
R(S) & Σ 320²
(2(S) ((T,0).
(36)
aES
Proceeding similarly for I, we obtain
802
R(T)= <
g gT, 8):
(37)
nh
acl
and for O we obtain
80 (T, 8) 32a ((T,))
R(O*) < max
(38)
1
(2
a
Then,
20 log
4k K5áqo
20 log
1ki Kdr=
R(O*)
Σ 16 max
(2
a
Σ a
16 max
2o
202
log
4kjKdTTa 8
Σ
320
log
15/dd)
n2
A2(
m
aEo
25

---

Constrained Pareto Set Identification with Bandit Feedback
Putting together (38), (37) and (36), yields
0 A (S)2
0²
20
20
R([K]) < 16
Σ
2 max
Σ
((T,0) + H(,,1),
(S)
1/a
O.EO
aES
aEI
+ (V,, I)
where (v, > Lnervo-
32m log(5") jd)
Therefore, assuming (35), we have proved that
42
T + S,C(u,,,T)CCC (T,,
(in T)
<
2
Then, taking T such that the RHS is smaller than T would yield that the algorithm stops before T. Applying Lemma D.1 with a - 6lo²C(v, S, a) and (4k; K Kd/5)//a yields
T log (ab) = a log(bT) T,
that is, letting S(,,S,1) = (v S,1)a
T > ((4 =
<T
(39)
</4.
(40)
Moreover, we trivially have for T 4H, H(v,I) T/4. Put together with (39), for T (* 2Č,,,S, log before round T. Therefore,
+ (H I), we have min(rs, T) T so the algorithm must have stopped
vA T (S, To (
that is [Ta] (S,,)) + (c)))) P Letting Ao Σr> (P((())))) and S, / is arbitrary, we have
Ex[Ta] < min T"" (S,1) Ao (5.1)EM
and from lemma D.3,
28-18
[(T,ō (01,,ödff0 -d/5) + ((T,)) Ta-1
Aa
(log(T) +1)
4kg
By definition the function f. we have f(T, 8 f(T 1 2 and 8 log(1/5) & 1/e permits to obtain the following upper bound, which now independent from 8:
f(T,
Using that 0 <
20-1
[[(T,5 + (TT, 1) + 2e 20-1
Aa
(log(T)+ +
4k
Ta-1
Finally, I log(z) is increasing (1, oo), we have
[T] & (2 (BCCC//))))(((CCCC))))4444444400 (" Aa
D. Concentration Inequalities and Technical Lemmas
We state some concentration inequalities that are used in our proofs.
Lemma 4.2, Under &s. for all i.j it holds : (i) jM M(i.j:t) & (((t) + By(t) and [m(i.j) - m(i.jtt) <
(1()) + (t),,, for any C Rd, (Ji, X) - dist (p4, & (t))).
26

---

Constrained Pareto Set Identification with Bandit Feedback
Proof.
[M (()
< max c
(1f - -19) (Pi pi.)
= max (15 - 111,)) - (n3 - -pia)
cgd
(1) + 9y(0),
where the last inequality follows under & Further noting that m(i,.) -- M(i,j) and m(i,j::() M((i,j:)) proves the first point. Letting X RR non-empty we have for all arm i
( 2) - dist(u;;
sup 1-11ps - x/|2] sup xEX
[-1l,r, x1|2]]
=E
sup #EAt
|ll - x|12 - 1lps xil
A3
|| uilll
W
(1,
where the last inequality follows from & (i) follows from the inequality
ssup / - sup gl < suplʃ - g
and (ti) follows from the |||=|||
|yll|
|a
vll-
Lemma D.1. Let a, b d The following statement holds
2a log(ab) = a log(bb)) <
Proof. First, note that t + log(bt)/t is decreasing on le/b, +oo) and observe for to = 2a log(ab), it holds that
log(btt)
Alog(aab: (ogg(ablog(())) log(ab))
log(ab) log(( log(ab)
2a log(ab)
(as log(x) x/2)
to
therefore, log(to) 1 and as the function is decreasing to
(bt(
log(bto) 1.
t to
to
We recall the following result of Katz-Samuels & Scott (2019), which has been used in the proof of the lower bound. Lemma D.2 (Lemma F.2 of Katz-Samuels & Scott (2019)). Let E Rd and S Rd be closed non-empty set. Then there exists S such that || yl dist(x, S). Lemma D.3. Let ((1,0) log(
4k Kdtt
1, 5) = 4 log( 4h k3*2
with ki > 1 + 1.
Then for all T we have
8
8
(?)
8 ( 1-a
Pp((ET) &
(log(T) + +)f((T,)) +
(log(T) + +1f 8 d//5),
4k1
4k1
2
where ET = serr &x. And, holds that (()))) < 8.
27

---

Constrained Pareto Set Identification with Bandit Feedback
Proof. Let X, denote the sample of centered o-subgaussian variable X based i.id observations. We have by
Theorem of Garivier (2013),
Pv la Ll: Vx 2
2e (((,)) exp((((()))
2ef(t, ()log() + exp( (x(p(((((66)
and by the proof of Proposition 5.9 in Kaufmann (2014), it holds that for any T
T
Σ
(t, 8)(log( + +x < {T(oT, (x)xpp/)))))ppp(((11110000
t=1
therefore,
Pv T, <:: v= f202f(t.5)
(T (log(T)) eeep(=ff(/22)0)
5
T
(log(T) ()
4k Kd
Kd
2
Thus, by union bounds over K, d we derive for vector valued subgaussian random variables,
8
T
1-a
Pr 31 < < E [K] || millo > f(1,
(log(T) + 1))(TT
4k1
For the second part the event ET, note that by Lemma F.4 of Katz-Samuch & Scott (2019), for any Rd centered valued random vector
Pa > o(t,))) & P, aL (#b)N())
I- _ XT= g((,5)
where M(e) is subset of the unit R& sphere and is an s-net e-cover of the unit Rd sphere with ((() (2/e + 1)d (ef Lemma F.5 of Katz-Samuels & Scott (2019)). Then, noting that XT is nu-usssasuuaaanii and taking e = 1/2, we have
Pa U(t E E 1XT2|> V ft, d/5d)
Thus, by what precedes and applying union bound over. (111)) and [K] we have
5
T
1-a
P,
3 & T, e [K] | Hill > V
6 (
(log(T) + 1)f(T, 8 dd/5"),
4k1
2
0.0.8)
where we used the fact that [W((12) < 54. Therefore,
8 T
8
[
P (EE &
(log(T) + 1))( +
(log(T) + 1)5(T, ()/5")
4k
2
4k
2
It remains to prove the last claim of the Lemma. By Hoeffding's 's sub-gaussian concentration (cf'..g (2020)), we have
Lattimore & Szepesvári
P, 3t 1,3i E [K]
[d] |2f, all (t(t,))
2Kd
exp( (xp(-f(tt,))
t11
1
2
to
t>1
28

---

Constrained Pareto Set Identification with Bandit Feedback
then, remark that Σi>1 1 & J 1- - and K > 1 --.. that
0
P. (31 1, E [K] 3e [d] 104, 1 > B:(1,)) <
Showing that
Pv ( 1, [K], |ic Hell2 > U, 6))
<
2
follows similarly by using the covering technique explained above. (v(())) < 8.
Combining the two displays we conclude that
E. Gap-Based Lower Bound on the Sample Complexity of e-cPSI
In this section, we prove lower bound on the sample complexity of any å-correct algorithm for the constrained PSI problem. As this is pure exploration problem with multiple correct answers, it might be tempting to apply Theorem I of Degenne & Koolen (2019). However, their result does not directly apply to our setting as the authors studied the regime 5 > O and considered answers that are singletons of [K] while we consider partitions of [K].
We state below the result we will prove in this section. We denote by D family of bandit instances that will become explicit by the end the section.
Theorem E.1. Let P = fa Rdd Ar b} and let E DK with means je I The following holds for any 8-correct algorithm
(1) 9(0) where g(0) = kl((1 5))2, (1-6)
Ev
min (8'P
log(1 (1/)) - 1og(2).
2
In particular,
[r]r]
CM(())
lim inf 6-40 log(1/6)
In what follows, we consider As, a 8-correct algorithm (cf Definition 3.3) and μ,, bandit instance, fixed and unknown to the algorithm. We assume that 5 < co almost surely (otherwise the lower bound trivially holds). Let Ô, S, 7 be the recommendation the algorithm after r (random) steps and F, the natural filtration of the stochastic process (Ar, Xt) stopped round 7. Since is 8-correct, the following statement holds
P. (ō= O and (8,T) M) > 11
(41)
We define
3 = E [K] us E P and 3j E O" 144 - μg}
the set of arms that are feasible but sub- optomml Note that alternatively, S SubOpt F. Similarly, we introduce
7= fie E [K] m & P and Àj E O² Ie x13b,
the set of arms that are unsafe but not uniformly worse than any other optimal arm, which rewrites as 7= O SubOpt..
In particular, 5 n = 0 and can be observed that for any valid answer (S,T) C M, S c and 7 c Thus, for any 8-correct algorithm it holds that
ViE P 21 and vi Vi Po E 9) 1-8.
(42)
Then by definition, every arm of = (0)) ( ()) can be (correctly) classified either in S or î, resulting in 2 correct answers, which can be up to 2 correct answers.
29

---

Constrained Parcto Set Identification with Bandit Feedback
E.I. A high probability correct answer for As
We describe particular correct answer under bandit y with mean l that is very likely be recommended by As. We build on (S.I) I) to construct a partition with (5,1) for which a property similar to Equation (42) holds for every arm
of (5, I). To construct such instance, note that as As is 6-correct, for any i E B (0*)² (S u 1)., holds that Puli f) > 1 - 6, which yields
max (P > 2
1-6
(43)
Then, define S, I as
s = S=SU((EEC:P(EE)>>>R.
and we similarly define the set
I == Tu T P N)
= 0 and SU I = (0r),, ie (5, I) is valid answer. Moreover, can verify that By construction, (S, I) satisfies Sni=
a) P= = 0-) > 8-8
b) for all i P. E 1 and
c) for all i EI i) > 2
that is this particular (0", S, 1) is a likely response for the algorithm As. Using change of distribution lemma will allow to derive a lower bound on the number pulls of each arm for As to identify (S, as a correct answer. In the sequel, we restrict ourselves bandit with multi-variate normal arms and identity covariance. Therefore, each arm will be identified with its mean vector.
Lemma E.2 ((Kaufmaan et al., 2016)). For all bandit models v. v and for any meassuuueale event E,
EN[N,, KL(V,14) > (().
where KL(V;, is the Kullback-Leibler divergence between distributions Vs, vi and is the relative binary entropy.
E.2. Change of distribution
The idea now is to apply the classical change of distribution lemma to different well chosen instances of bandit. We define ...,,, A such that A = (Af) k and X differs from μ only in the mean of arm i i... the bandits and are identical except Ex=et [X] x # ps = Ex=,, For such instances, applying Lemma E.2 yields
instances with v/ ,,,.... 2 with (matrix of) means (resp.) A !.....
E, KL v/) > sup (() EEF,
(44)
where in our case, KL(H,, Af) is the Kullback-Leibler divergence between multivariate normals of means v4, va and identity
covariance. kl y) == x log(æ/v) + (1 - x)) log((1 - / y)). and noting that x +> kl(æ, y) increasing on {x > y) and decreasing on (x < w). making an event likely under v unlikely under of will increase the RHS of Equation (44). Going back the instance (S, I) constructed earlier, we introduce the event
i
=
{iEî)
ifiel,
(0=-0))
i
30

---

Constrained Pareto Set Identification with Bandit Feedback
We recall that (O*, forms partition of [K]. From the definition of (S,1) we have shown that for any d-correct algorithm,
i
(E
else.
that is such an event is very likely under bandit μ. We will choose each instance X such that & is unlikely under bandit X i.e we assume that X is chosen such as for all i
P. (E;) E 6.
(45)
We now discuss the choice of X depending on i to ensure such property. Thus, assuming this property holds, have for all arm i
1
[N[N KL 1/) > kl
2
which using the KI formula for multivariate normal yields
8
E, [N
kl
[44
X
2
9(6)
an unsafe In this case, 14; & P. Since P is closed convex set, by Hilbert projection onto closed convex sets, there exists (ef Lemma D.2) P such that || 2:|l2 dist(ps: P). We now define X; 24. In this bandit As i is now safe arm so, as As is 8-correct algorithm it holds that
Case 1:
Pp E < 8 i. (.) < 6,
which by further noting that ||I - Xill2 = dist (1s P) = results in
NN > m/
(())
Case 2: i S sub-optimal arm. Note that in this case, there exists a subset Q C O' such that μ4 Mj for all E Ωz it is the set of optimal arms that dominate μr. For any j E Ω4 we define
argmin (c)(c) [4(c)]
the coordinate for which the margin between and j is the lowest. In particular, mii = m,(c;) - -M(ce). Moreover, for any 0, the vector defined by
(i(e) + (1+ ifc (i(e)
(.(c)=
else
not dominated by My. Now us define the vector 8; such that for any e E (d]
(c(c)
max JER
m(i,j)
(46)
with the convention that max 0. We argue that defining
= Mi +
we have
(i 5) 8.
To see this, note that as only the mean of arm i has changed between bandits v and vA the set of feasible and infeasible arms of [i] under and of are the same. Moreover, the change of distribution ensures that under the bandit vτ, i is not dominated by any feasible arm. Therefore, Pii(i E 5) < 8. So applying what precedes and letting - 0 yield
2
[v[Nr >
|>s g(0).
(47)
31

---

Constrained Parcto Set Identification with Bandit Feedback
Case 3: O" the optimal set. We recall that arms in O are both feasible and Pareto optimal among feasible arms. We then build alternative instances where arm i E O is either made infeasible sub-optimal among feasible arms under bandit v'.
Letting 77: = dist( Pc) = dis OP) (as b4 E P, of (16)) and since aP a closed, using Lemma F.2 of Katz- Samuuls & Scott (2019) (recalled in Lemma D.2), there exists 2; E 0P such that dist( QP) = |/4; - z:|12 = 7/s- Then, note that, as 24 $ 8e (the interior of P), for all e > 0, 3zf E p such that || - z;ll & E. Then, letting A = 2 (for some fixed). comes that is infeasible under X², so that Pa (E,) < Therefore, we have
2
[N,,
| 25 211129(0)
=
| - + (2i 2$ 21)129(0)
Letting E - 0 yields
2 |14 =1112(00) m -
2
[N >
Alternative change of distribution will prove the dependency on the other quantities involved in the gaps. Assume the gap of is attained for an arm O with A, = j). In this case, j is close to dominating i so that decreasing will make dominated by j. as result, i becomes either feasible but dominated or non-feasible, i.e i O in both cases. We define in this case
X = μ4 - (1 + +) 15)+
where (x)+ is defined womponent-wise for z R Then it can be easily checked that under bandit v², arm i is now dominated by and j is still feasible. Therefore, P, (E.) & (i E Ō) & 6. So that proceeding before we prove that
2
[N > [14 pb)+ 12
(48)
Similarly, if we had A; M(J,) for some j O", Then, increasing i will make it dominate j. Thus, defining
X μ4 + (1 (1+))(mg- -140)--++++++ ++
on can observe that arm j is now dominated by under bandit v'. Note that j is still feasible in bandit s' (since its mean has not changed). So two things may occur. Either i is still feasible under v², in which case j is feasible and sub-optimal in bandit v or is now infeasible under bandit v so that is no longer optimal arm, In both cases, the optimal set has changed, so that IP, (E.) & 6. Reasoning as in the previous cases,
E,
> [[u (4) 11)1))1(0)
(49)
Therefore, by defining the quantity we have proved that
2
E. [N.a)] >
min(,, m2)2 g(0),
where
8+
min min(1(( p+)++ 12, 1(: p1)++12) (E)
(50)
Note that this is a strictly positive quantity as i E O and from the definition of non-dominance for all j E O
E.3. Relation to the gaps in PSI
We recall the expressions of the PSI gaps (w.r.t O*) as introduced in Auer et al. (2016). For sub-optimal arm i E S,
A
A
max m(i,)),
(51)
JEO
32

---

Constrained Pareto Set Identification with Bandit Feedback
For an optimal arm E 0
A((SU0") min(6, :
where
6= = min min(M(i,)) M(j and (5) = mini (M) + +, SEO
JES
and M(i,j) max (mi(c) - [y(c)]. Since O is fixed, case notation and write A,(SUO*) A.(S) for all i O
As justified in Remark 18 of Auer al. (2016), o7 (S), can be compensated by both 65) and Aj for arms j E SubOpt (in our case). So we focus on matching the gaps in of for E O Moreover, from the definition of M(i,j) for for i,j E O (and from the definition of Pareto dominance), can be easily checked that for any i O
min min(l p1)+llo (1 1y)+1lao)
(52)
JEO-M
Intuitively, (in the case of independent objectives), (50) suggests to measure distance between Pareto optimal arms in Euclidean whereas (52) measures in sup norm. As these quantities are computed over Pareto optimal arms, it can be checked that for d = 2. both terms are equal. the worst case, the discrepancy between 6, and of is at most vd. However, as we discuss later, there are classes of PSI/constrained PSI instances where these quantities are equal.
Similarly, one can check that for sub-optimal arm, the discrepancy between A and ||s; ||² (46) is most min(y / [ d), where recall that
Ω = (j 5 μ4 < kドン}.
Thus, instances where Q2 is singleton, that is each of SubOpt is dominated by a unique feasible optimal arm, ||s/||2 and A are equal. To summarize, we have been justifying that under the following.
e 0" 8. = 5.
and
Vi E SubOpt, ||8:|12 A
(53)
combined with the results of sub-section E.2 would have
ife
E, x
if S
(54)
if 0
Then, as [x[T]= EK [NN.))
Ex[T] > C(v,S,1)g(0).
where we recall that
C(v,S,1)= = Σ SEO+
2
Σ
+
min(A,(('))) US) m ))
(A(O*US)) IES
NEl
Finally observing that (S, I) is an arbitrary correct response yields
[-[T]
min (STP))MM
C(v,S",
(55)
and observe that g = kk((k(11111 (L((1-6)/2,6) > (1-6) log(1/0) - log(2) (as kl(æ, 8) > x log(1/v) - log(2)).
E.4. Conclusion
We now give examples of families of instances constructed to satisfy (53). This includes, e.g, instances where the means vectors are close in many objectives except a few (2 or 3). To give more intuition, we build some examples below. We let D be the family of multivariate normals with identity covariance and whose mean vector Pı. MK is as below.
and d (arbitrary). Define #1 No and for any i K, p ph and 2 = 1 and μ μg for all & {1,2}. Such sequences of vectors are non-dominated by each other and direct computation yields for any E [K]
Let a and let Ho
2a and 8 = a.
33

---

Constrained Parcto Set Identification with Bandit Feedback
Thus, for E O the discrepancy between 5 and 67' is 2, irrespective of the dimension. As for such instances, for any P. either have E O 14 P, so, (55) is satisfied with extra multiplicative constant 1/4.
Put together, on this set of instances we have
min C(u,S', 17) 77) (s
, 9(0)
Fu(r] 2
(56)
which gives the claimed result
lim inf Ev|T] log(1/5)
CM(p)
F. Racing Algorithm for Constrained Pareto Set Identification
We describe the pseudocode of the racing algorithm, and we comment on its performance. As for racing algorithms, an active set is initialized with all the arms, and the algorithm uses confidence bounds to sequentially discard some arms, The reasons to discard an arm are
1) it is confidently infeasible
2) it confidently dominated by another arm that itself is confidently feasible
3) it is confidently optimal (in the Pareto Set and feasible) and with high confidence does not dominate another active arm,
Three sets Ō,3,ī are initialized empty, and when discarded, depending on the reason for discarding, it added to one of them.
Algorithm Racing for constrained Pareto Set Learning
Initialize: A + 0, Ô + 0, S - 0, for t 1,2,... do
if A, 0 then
break and return T,
end if
Pull each active arm once
Compute Y (t) for each active
7 - fifiE A, jue. & P and vi(() > 0}
$ S- --ff A, }j A S.L. Pr E Pt))(t) > 0 and m (i,j;t) 0}
pt < A E (. 0}
De (i VVj E A)) 0)
Ô ŌufiEr E E and 7(1)> >
A - ANOUSUI
+ ++1+1
end for
The proof of the correctness of this algorithm follows the same lines as for e-cAPE using concentration inequalities on the quantities m, M.
Limitations of Racing for cPSI One major limitation of this racing algorithm for constrained PSI is linked to the second reason for discarding an arm (as listed above). Indeed, assume O² As the algorithm is d-correct, on most runs, will be added to S. So before discarding, we ensure that is dominated by an arm that itself is already known feasible. This sub-optimal for an algorithm for constrained PSI. To see this, let us build an instance such that == [K] and O = =1} (w.Lo.g). Further assume that Par[[K]\[1}, (4) [K]][], i.c., the remaining arms are not dominated by each other. In this instance, all the arms are feasible, and only is Pareto optimal. Therefore, before correctly removing any arm k * 1,
34

---

Constrained Pareto Set Identification with Bandit Feedback
the algorithm will ensure that it is dominated by and is confidently feasible. Thus, all the arms would be pulled least until 1 appears confidently feasible. The sample complexity of the algorithm this instance will thus scale with
20
(2K
[[K]]
while the sample complexity of cAPE will scale with
2a
20 7i
(
This observation further confirmed empirically Appendix G, where both algorithms are benchmarked on similar instances.
G. Additional Experiments
In this section, we present the results of some additional experiments and further discuss the computational complexity of our algorithms. All the algorithms were mainly implemented in python 3.10 with some functions in cython for faster execution. The experiments were run on an ARM64 8GB RAM/8 core/256GB disk storage computer.
G.I. Experiments on complex polyhedra
We evaluate our algorithm on different polyhedra in RS; an ordering polyhedron Pi = E R$ : & 8141iE E [2]] simplex P2 = {ir E R xy > and Σ; xz & 1} and finally a cube P3 = {-r E R$ 0.15 < x, < 1, E []]. For each polyhedron, we define multivariate bandit instance with means and feasible region depicted in Figure 5.
We report in Table the sample complexity of e-cAPE against that the two-stage baseline and uniform sampling. We see that by focusing on responses with minimal cost, e-cAPE consistently achieves superior performance in experiments. In some experiments, the uniform sampling approach combined with our stopping rule outperformed the two-stage algorithm. This outcome is anticipated, as our stopping rule is designed to trigger once any confidently correct answer can be identified. These findings underscore the competitiveness of both our sampling and stopping rules.
Table Sample complexity of algorithms averaged over 500 seeded runs.
Algorithms' empirical sample complexity
Experiment
e-cAPE
MD-APT+APE
Uniform
Mean
Std
Mean
Std
Mean
Std
Simplex
2679
517
4886
873
12156
2428
Hypercube
19034
3158
59841
10186
56184
14392
Ordered polyhedron
4313
693
7183
792
11895
1932
0.
64
Rosten Featlo Outrnal
Figure Constrained instances with (left to right): ordered polyhedron, cube, simplex. The green area denotes the feasible region.
35

---

Constrained Pareto Set Identification with Bandit Feedback
Time and memory complexity of e-cAPE Since only the empirical means of the sampled arms by, ct change in each round, the Pareto set can be updated in time O(Kd) and only the feasibility gaps of bt are updated round t. We recall that a OP) has closed-form and computing di P) is quadratic program that can be solved efficiently with libraries like CVXCPT. The memory complexity is O O(K2), allocated only at initialization to store M(i. j; ())])( In Table 5 we report the runtimes of e-APE compared to that of the two-staged baseline and of uniform sampling.
Table 5: Runtimes of the algorithms averaged over 10 runs the same instance.
Algorithms' runtimes (ms)
Experiment
e-cAPE
MD-APT+APE
Uniform
Mean
Std
Mean
Std
Mean
Std
Dose finding (Figure 2)
2759
31
54890
381
3787
24
Hypercube
12300
9
18000
2970
2000
28
Simplex
672
13
2890
52
7543
57
Ordered Polyhedron
4010
7
4460
20
10200
40
G.2. The cost of explainability
In this experiment, present the result of preliminary experiment to "compare" e-cAPE with Game-cPSI (Algorithm 2) our asymptotically optimal for the cPSI objective.
The two algorithms are not designed for the same objectives, but we can start to compare them for the simplest cPSI one, by evaluating e-cAPE only on its final guess Ö, for O" (H.) Since e-cAPE is designed for the explainable case, is expected have a larger sample complexity. We evaluate both algorithms on a 5-armed Gaussian instance in dimension 2 with means given Figure (left). We 0.01 and report in Figure 6 (right) the distribution of the sample complexity over 250 seeded runs.
0.8
10,000
O"
S
0.6
8,000
<2 0.1
6,000
0.2
x
2,000
0.0
0.0
0.8
e-cAPE
Game-cPSI
Figure Constrained PSI instance (left) and distribution of the empirical sample complexity (right) averaged over 250 runs.
Sample complexity Quite surprisingly, on that instance the sample complexity of e-cPSI is actually (slightly) smaller than of cPSI, despite the fact that the latter is asymptotically optimal for cPSI. There could be several explanations to this phenomenon: the performance of cPSI could be not so great in the moderate confidence regime, that is, for fixed value of ó not tending to zero. Or, on this particular instance, the complexities of cPSI and e-cPSI could be close. This phenomenon will be investigated in future work by considering a larger benchmark.
Error probabilities Additionally the sample complexity, it is interesting to look at the empirical error, for both the cPSI and the e-cPSI objective. We let òn denote the empirical correctness for the e-cPSI problem and ån for the cPSI problem. By definition, we always have 6, & 82. Although Game-cPSI is not designed for e-cPSI we can use its empirical infeasible set and empirical feasible sub-optimal to form a complete recommendation for e-cPSI. For this heuristic variant of Game-cPSI, we have reported (8, 82) = (0.39, 0) while for e-cPSI we have reported (81, 82) = (0.01, 0). We remark that both algorithms are correct for their respective task. e-cPSI is by design also correct for cPSI, while the heuristic
36

---

Constrained Pareto Set Identification with Bandit Feedback
version of Game-cPSI does ô-correct for e-cPSI, suggested by the empirical results. This suggest that there exist intermediate regime between ePSI and e-cPSI where the learner identifies the feasible Pareto Set before classifying the remaining arms.
G.3. A Hard Instance for Racing
In this experiment, illustrate the limitations of Racing algorithms for constrained PSI as argued in Appendix F. We run the experiment with K = 5 and K 10 in dimension 2 Bernoulli instances. In both cases, keep the same polyhedron, which corresponds to half-space delimited by the axis. The instance is chosen such that each arm is feasible and there is only one optimal arm. We set ő = 0.01 and we reported negligible emror. Each experiment is averaged over 250 runs.
033
0.55
00
0.01
30,000
0.50
10,000
RCCP
E-LAPE
A.A
R.CP
Figure 7: Constrained 5-armed PSI instance on the left and em- Figure 8: Constrained 10-armed PST instance the left and em- pirical distribution of the sample complexity (right).
pirical distribution of the sample complexity (right).
First, we mention that in this kind of instance, both e-cAPE and the two-stage approach have a closed theoretical sample complexity (in particular because the feasible sub-optimal arms are far from the borders). The results of Figure 8 show in this regime, Algorithm 2 is largely outperformed by e-cAPE expected. Even the two-stage algorithm outperforms Algorithm 2 in this regime.
37


Reviews:
[{"review_id": "rN4ngDXx16", "reviewer": "Reviewer_7kAg", "summary": "This work studies bandit pareto set identification with constraints. In particular, the task is to choose arms to pull in each round until the set of feasible and pareto arms is identified with probability at least $1 - \\delta$. They give an algorithm that addresses this problem\n\n## update after rebuttal\n\nIn the rebuttal, the authors clarified the meaning of $\\lambda_\\alpha$, and provided an additional result that doesn't require that $\\delta$ shrinks exponentially in $d$. Regarding the clarification of $\\lambda_\\alpha$, I found the authors' explanation to be sound and quite helpful in general. Regarding the additional result, I do think that this alleviates some of the restrictions of the original result. However, one downside of this result is that we can't say much about the tightness (although this is not true in the reasonable setting where $\\delta$ is small). Overall, I maintain my original score, as I think the results are good overall, but there are some points of weakness.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's thoughtful feedback and detailed evaluation of our work. Below, we specifically address each point raised in the review. \n\n1.  $α$ is a parameter of the algorithm. We introduced generic confidence bonuses in l.255-l.257, and Thm 4.3 upper-bounds the sample complexity of e-cAPE when it is run with confidence bonuses in the form described in the statement (depending on $α$). In practice, $\\alpha$ is set at the beginning of the algorithm. We give additional clarification on $Λ_α$ in the answer to question 2 below. \n\n2. We thank the reviewer for this insightful comment. The condition on $δ$ is actually loose and can be removed (at the cost of an additional second-order term, independent from $δ$). First, we would like to mention that this condition was actually needed only for the sample complexity bound and not for the correctness of the algorithm (e-cAPE can be run for any $δ$ and outputs a correct answer with probability larger than $1−δ$). We acknowledge that this is unclear from our current statement of Thm 4.3.\nThe term  $5^d$ that appears in the calibration function $g(t,δ)$ is due to the covering number of the unit sphere, which arises from L2 norm concentration with the covering technique. The condition on $δ$ appeared from a sub-optimal upper bound on $g(t,δ)$ in the proof, specifically in l.1300. To see how this can be improved, we sketch below the proof of Thm 4.3\n\n  * **Bounding the stopping time under consecutive good events** \n  Let $τ$ be the (random) stopping time of e-cAPE, and observe that for any $T>0$, \n$$\\min(τ,T)⩽T/2+\\sum_{t=T/2}^T\\mathbb{1}_{(τ>t)}.$$\n\nIn Proposition C.3, we show that if the good event $E_{t}$ (defined in l.255-256) holds and e-cAPE does not stop at round \n\n$t$, then for any correct answer $(S,I)\\in M$, either $b_t$ or $c_t$ is underexplored (i.e. not pulled enough wrt some gaps that are function of $S, I$). This is expressed by saying that $\\\\{b_t,c_t\\\\}\\cap W_t(S,I)\\neq ∅$; $W_t(S,I)$ is defined in equations 37-39 (l.980-83). Assuming $$E^T:=\\bigcap_{\\frac{T}{2}⩽ t⩽T}E_t$$ holds and fixing an arbitrary correct answer $(S,I)$, we have  \n\n$$ \\min(τ,T) ⩽ T/2+\\sum_{a=1}^K\\sum_{t=T/2}^T\\mathbb{1}_{((b_t=a\\lor c_t=a)) \\land (a\\in W_t(S,I))}.$$\n\nIntroducing for any subset $U\\subset[K]$, \n\n$$R(U,T) :=\\sum_{a\\in U}\\sum_{t=T/2}^T\\mathbb{1}_{((b_t=a\\lor c_t=a)) \\land (a\\in W_t(S,I))},$$\n\nit follows from the definition of $W_t(S,I)$ (equation 37-39, l.980-83) that \n$$R(S,T)⩽\\sum_{a\\in S}\\frac{32σ^2}{\\Delta_a^{2}(S)}f(T,𝛿);R(I,T)⩽\\sum_{a\\in I}\\frac{8σ^2}{\\eta_a^2}g(T,𝛿)$$ and  \n $$R(O^*,T)⩽\\sum_{a\\in O^*}σ^2\\max(\\frac{8g(T,𝛿)}{\\eta_a^2},\\frac{32f(T,𝛿)}{Δ_a^2(S)}).$$ \n   * **Former sub-optimal step and novel formulation of Thm 4.3** \n  \nAt this step, the idea was to write $R(O^\\star)$ a sum of terms in the form $\\sum_{a\\in O^*}\\max(\\frac{1}{Δ_a^2(S)},\\frac{1}{\\eta_a^2})h(T,𝛿)$ (this would further make appear the complexity term $C(S,I)$, cf Eq.11 (l.311)). \nRecalling $$f(T,𝛿)=\\log(\\frac{2k_1KdT^α}{𝛿})\\text{ and }g(T,𝛿)=4\\log(\\frac{2k_1K5^dT^α}{𝛿}),$$ \nthis is where we used the condition: as for $𝛿⩽ d^2/5^d$ we have \n$\\log(5^d/𝛿)⩽2\\log(d/𝛿)$ and $g(T,𝛿)⩽ 8f(T,𝛿)$; and we set $h(T,𝛿)=8f(T,𝛿)$. To fix this loose step and remove the restriction on $𝛿$, observe that \n$$R(O^*,T)⩽\\sum_{a\\in O^*}32σ^2\\max(\\frac{1}{\\eta_a^2},\\frac{1}{Δ_a^2(S)})f(T,𝛿)+Q(\\mu,O^*)$$\nwhere $Q(\\mu,U)=\\sum_{a\\in U}32σ^2\\frac{\\log(5^d/d)}{\\eta_a^2}$. \nApplying the modification above and following the remaining proof of Thm 4.3, we prove that for any $𝛿\\in(0,1)$,\n$$\\mathbb{E}[τ]⩽256σ^2 C^*(\\mu)\\log(128σ^2C^*(\\mu)(2k_1Kd/𝛿)^{1/α})+4Q(\\mu,F^c \\cup O^*)+Λ_α$$\nwhere $F$ is the feasible set. \n\n * **Additional Clarification on $Λ_α$**\n \nBy definition, we have (l.1330) $Λ_α=\\sum_{T⩾ 1}\\mathbb{P}((E^T)^c)$. We showed above that when $E^T$ holds,  \n$$\\min(τ,T)⩽ T/2+R([K],T)$$ then, letting $\\tilde T$ such that $\\forall T⩾\\tilde T,R([K],T)<T/2$,  \nfor $T⩾\\tilde T$, $τ >T⟹ (E^T)^c$. Thus, \n$$\\mathbb{E}[τ]⩽\\tilde T+\\sum_{T⩾\\tilde T}\\mathbb{P}((E^T)^c)⩽\\tilde T+Λ_α,$$ and $Λ_α$ is bounded using Lem D.3 in appendix. \n\n3. We appreciate the reviewer's insightful observation. Indeed, our approach could be extended to general convex feasible sets. However, the main challenge would be computational. Specifically, for a feasible set $P$, our algorithm should compute at each iteration, quantities such as $dist(x,P)^2$ (squared Euclidean distance to $P$; convex quadratic program with linear constraints) and $dist(x,P^c)^2$, which is not always convex, making it significantly more complex in general. In the special case of polyhedral sets, the latter distance has a closed-form expression, simplifying computations considerably. Additionally, another computational aspect (albeit minor) is the verification oracle for membership in $P$. Given that polyhedral sets encompass many practical scenarios while ensuring efficient algorithmic costs, we chose to focus the presentation on this setting.", "claims_and_evidence": "I have some concerns with the interpretation of the sample complexity bound. In particular, I'm not sure the claim of \"near-optimal\" is justified given my concerns detailed in \\# 1 and \\# 2 in the Questions box.", "methods_and_evaluation_criteria": "Overall, the approach seams reasonable, and the use of sample complexity to evaluate the algorithm is reasonable.", "theoretical_claims": "I did not check the proofs, but have some concerns with the interpretation of the theoretical results as discussed in the Question box \\# 1 and \\# 2.", "experimental_designs_or_analyses": "There are no experiments.", "relation_to_broader_scientific_literature": "To my knowledge, this works contributes a new problem setting to the literature, combining the pareto set identification problem with the feasible set identification problem. Accordingly, their approach appears to be novel.", "essential_references_not_discussed": "None that I saw.", "other_strengths_and_weaknesses": "No others.", "other_comments_or_suggestions": "1. I would suggest putting a definition of the Pareto optimal set $O^*$ in Section 1.1. It would be preferable for this to appear before it is referenced in line 97.\n2. There is an unfilled reference XX in line 85 right side.", "questions_for_authors": "1. The sample complexity guarantees in Theorem 4.3 are shown to include a term $\\lambda_\\alpha$ which looks to be $\\tilde{O}(\\sum_{T \\geq 1} \\frac{1}{T^{\\alpha-1}})$ where $\\alpha$ is a free quantity restricted to $\\alpha > 2$. It seems that the claimed regret bounds would require that $\\lambda_\\alpha = \\tilde{O}(1)$, but I don't see how this would be the case when the factor $\\sum_{T \\geq 1} \\frac{1}{T^{\\alpha-1}}$ could be as large as $\\sum_{T \\geq 1} \\frac{1}{T}$. Maybe it is just not clear to me what the summation $\\sum_{T \\geq 1}$ is over exactly.\n2. The sample complexity guarantees in Theorem 4.3 also restrict the confidence level $\\delta$ to be in the range $\\delta \\leq \\frac{d^2}{5^d}$, which depends exponentially on the dimension. This seems to be highly restrictive, especially in high dimension settings. Can this be avoided? I didn't see this requirement in related work.\n3. Can the approach be extended to convex sets? I did not identify any specific arguments that restricted the algorithm or analysis to polytopes.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tk8idVsChv", "reviewer": "Reviewer_DwcZ", "summary": "This paper studies the constrained Pareto set identification (cPSI) problem (with explainability). More specifically, the authors focus on the $(\\epsilon, \\delta)$-PAC learning setting, and the objective of the agent is to identify a partition of the arm set into three sets (the Pareto set, a set of suboptimal arms, a set of infeasible arms). They derived instance-dependent lower bounds of the sample complexity for cPSI and e-cPSI. Then, they proposed an algorithm for e-cPSI termed e-cAPE. They provide the sample complexity analysis of e-cAPE and prove that it is nearly optimal for some problem instances, which implies that e-cAPE is nearly optimal in a worst-case sense. Using real-world datasets, they empirically show that the proposed method achieves smaller sample complexities for some problem instances.\n\n## update after rebuttal\nSince my concerns (questions) have been resolved by the author's response, I will keep my positive score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and for taking the time to evaluate our work. Below, we address each of the points raised in the review. \n\n* **Optimal algorithm for cPSI** \n\nWe present an asymptotically optimal algorithm for cPSI in Appendix E. Since we believed that e-cPSI was better suited for the applications we focused on, we initially placed the cPSI algorithm in the appendix. However, as suggested by the reviewer, we can provide more details on this algorithm in the main text if space allows in the revision.\n\n* **Uniform exploration**\n\nWe agree that an algorithm using uniform exploration could be worse-case optimal for certain very particular configurations of arms (but probably a much more reduced set of instances compared to the one constructed in our lower bound). Still, e-cAPE is designed to perform more efficiently by focusing on arms that are more likely to be part of the feasible Pareto Set rather than exploring uniformly. This adaptive exploration typically leads to more efficient identification of the Pareto Set, especially when the number of arms is large.  \nIn Appendix F, we analyze the limitations of an algorithm that performs uniform exploration and additionally discards some arms when their status can be deduced from confidence boxes. We show that for this algorithm (which is expected to be even better than pure uniform sampling due to the additional eliminations), there are some configurations where its sample complexity scales with a quantity that is order $K$ times larger than that of e-cAPE; with $K$ the number of arms. This provides some theoretical insights as to why the sampling rule of e-cAPE leads to a lower sample complexity compared to uniform sampling. \nMoreover, we do illustrate empirically the benefits of e-APE compared to both uniform sampling (see e.g. Table 5 in Appendix G.2) and uniform sampling with eliminations (see Figure 6,7 in Appendix G.2).", "claims_and_evidence": "Claims are supported by theoretical results (analysis on lower and upper bounds) and experimental results.", "methods_and_evaluation_criteria": "Theorem 4.4 shows the proposed method is nearly optimal for some problem instances and the evaluation metric for experiments is the sample complexity, which is standard for the PAC problem.", "theoretical_claims": "I have not checked proofs. At least, lower bounds seem standard results and valid.", "experimental_designs_or_analyses": "The experiments are conducted using real-world datasets and baselines seem valid.", "relation_to_broader_scientific_literature": "As the authors state cPSI and e-cPSI are practically important problem settings, such algorithms would be beneficial to the papers outside the ML community.", "essential_references_not_discussed": "To the best of my knowledge, related works are adequately discussed.", "other_strengths_and_weaknesses": "- Strengths\n    - The authors study practically important problem settings (cPSI and e-cPSI).\n    - Experiments are conducted on real-world datasets.\n    - The proposed method is near-optimal in a worst-case sense.\n- Weaknesses\n    - Although the proposed method is near-optimal for some problem instances, it is a worst-case analysis. I suspect, a very simple algorithm (such as uniform exploration) has a similar property.", "other_comments_or_suggestions": "Is an algorithm for cPSI asymptotically optimal? If so, since the current version of this manuscript has some space, you can include the claim even in the submitted version (and a revision).", "questions_for_authors": "1. As I wrote in \"weaknesses\", I think a uniform exploration algorithm can achieve an optimality in a worst-case. Is it possible to theoretically compare Algorithm 1 to such a simple algorithm?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZRLs2oE8gy", "reviewer": "Reviewer_meBs", "summary": "This paper studies the fixed-confidence setting of the Pareto Set under linear feasibility constraints in a multi-objective bandit setting. The authors propose an algorithm and establish its near-optimal theoretical guarantees through information-theoretic lower bounds in the worst case, and validate their approach through extensive experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's thoughtful feedback and detailed evaluation of our work. Below, we address each point raised by the reviewer. \n- Weaknesses\n  1. Linear constraints are widely used in applications like dose-finding trials, where balancing efficacy and toxicity is crucial (Mark C et al., 2013). Appx G.2 (Tab. 5) includes additional results on more complex set of linear constraints. Our guarantees also extend to general convex constraints, but we focus on polyhedral ones for their practicality and efficiency.\n  2. We would like to clarify that this condition was actually needed only for the sample complexity bound and not for the correctness (for any $δ$, e-cAPE outputs a correct answer with probability larger than $1−δ$). We acknowledge that this was unclear from our statement of Thm 4.3. This condition is actually loose and can be removed (at the cost of a second-order term in the sample complexity independent from $δ$).    \n  3. e-cAPE is mainly designed e-cPSI, but any $𝛿$-correct algorithm for e-cPSI is also $𝛿$-correct for cPSI; so is e-cAPE. However, as both tasks are different, e-cAPE is not necessarily optimal for cPSI. As noted in Section 3.1, we provide a dedicated algorithm for cPSI in Appx E, which is optimal as $𝛿\\to 0$. An experiment in Appx G.2 compares e-cAPE to this cPSI-specific algorithm for $𝛿=0.01$. e-cAPE performed slightly better in practice despite not being tailored for cPSI. If given additional space in a revision, we would include more details on cPSI in the main text to further clarify its theoretical and practical aspects.\n\n- **Questions**\n  1. We set $𝛿/2$ for each stage to maintain an overall $𝛿$-correct guarantee. We did not retain historical data from the first stage (feasibility identification) to the second stage (Pareto set identification) as it is unclear whether the claimed sampled complexity bound holds if we do. Through experiments on synthetic instances, we actually observed that reusing historical data from the first stage often introduced bias in the second stage, leading to an overall increase in sample complexity. Exploring more principled ways to leverage historical data while mitigating bias is an interesting direction for future work.\n  2. By this, we mean that the algorithm runs until the stopping condition specified in Equation (7) is met. We clarify that the \"Uniform\" baseline shares the same stopping criterion as e-cAPE; the key difference lies in their sampling strategies. Specifically, while e-cAPE adaptively allocates samples, the \"Uniform\" algorithm follows a round-robin sampling scheme, allocating roughly equal samples to all arms.   \n  \n  3. For $𝛿=0.1$, we report below the empirical success rate of each algorithm\n||e-cAPE|Uniform(U)|MD-APT+APE(A-A,Two Stage)|Racing algorithm(R-CP)|\n|---|---|---|---|---|\n|covboost|100%|100%|100%|96%|\n|secukinumab|100%|100%|100%|100%|\n\nAll algorithms achieve similar success rates, and e-cAPE, R-CP, A-A, implement the same confidence bonus function. \"Uniform\" and e-cAPE share the same stopping rule. As detailed in Appx G, in the implementation, we used the confidence thresholds advertised in Auer et al (2016). Although tighter than the one allowed by the theory, they remain very conservative.  \n  \n  4. $T^*_{M}$ captures the hardness of e-cPSI in the asymptotic (when $𝛿\\to 0$, cf Prop 3.4). As noted in section 3.2, an extension of Degenne and Koolean (2019) to e-cPSI would yield an optimal (as $𝛿\\to 0$) yet impractical algorithm (as it needs to solve up to $2^K$ max-min problems similar to Eq.(2) at each round, none having a closed form). This algorithm will satisfy $\\lim_{𝛿\\to 0}\\frac{\\mathbb{E}_{{\\mu}}[τ_𝛿]}{\\log(1/𝛿)}=T^*\\_{M}$. On the other side, $C_M^*$ is the leading complexity term in our lower bound and in the sample complexity of e-cAPE, for which the guarantees are non-asymptotic. By combining Thm 4.3 and 4.4, on the class of problems $\\tilde{D}$ (explicit in appx B), we have \n  $$C_M^*(\\mu)/4⩽ T^*_M(\\mu)⩽256C_M^*(\\mu),$$\n which shows that $C_M^*(\\mu)$ is a reasonable complexity proxy for problems in $\\tilde{D}$ (up to some improvable constants). \n\n  5. The computational complexity of e-cAPE is mainly determined by computing the squared Euclidean distance $dist(x,P)^2$, which we solve using MOSEK (via CVXOPT) in $O(\\max(m,d)^3)$ with $d$ the dimension and $m$ the number of constraints. Computing $dist(x,P^c)$ takes $O(md)$. If the state (quantities $M(i,j;t)^\\pm_{i,j},(γ_i(t))_{i}$,) is updated, $b_t,c_t$ are computed in $O(K)$. As only the means of $b_t,c_t$ change from $t$ to $t+1$, updating the state requires : \n* $O(n_t d+md)$ to update the feasible Pareto set ($n_t$: size of the feasible set).\n* $O(K)$ to update $M(i,j)^\\pm$\n* $O(\\max(m,d)^3+\\max(K,m)d)$ if $b_t$ or $c_t$ is empirically infeasible, otherwise $O(\\max(K,m)d)$ to update $(γ_i(t))$.\n\nPer iteration, the cost is linear when $b_t,c_t$ are feasible; otherwise, cubic in $m$. Memory complexity is $O(K^2)$ to store the state.", "claims_and_evidence": "I did not identify any errors in the theoretical claims presented. However, I discuss certain limitations of these theoretical results in  'Other Strengths and Weaknesses.'\n\n Regarding the experimental claims, please refer to my detailed comments provided in the 'Questions for Authors' section.", "methods_and_evaluation_criteria": "In the experiment, it makes sense to compare the empirical stopping time. However, it would be better to also show the empirical  failure rate.", "theoretical_claims": "I do not check the proof.", "experimental_designs_or_analyses": "The authors indicate that they conducted 500 runs for the experiments presented in Figure 4, and 250 runs for those in Figure 6. Could the authors also report the exact number of successful runs achieved by the agent in e-cPSI (or cPSI), and clarify whether these results align with the specified thresholds of $\\delta = 0.1$ (Figure 4) and $\\delta = 0.01$ (Figure 6)? Furthermore, to ensure a fair comparison, could the authors confirm whether the number of failures for e-cPSI (or cPSI) is approximately consistent across the evaluated algorithms in these experiments?\"", "relation_to_broader_scientific_literature": "The primary contribution of this paper lies within the domain of multi-objective multi-armed bandits. While most prior studies have concentrated on regret minimization or unconstrained Pareto set identification, this paper presents the first investigation into constrained Pareto set identification, even within the simpler setting of linear constraints.", "essential_references_not_discussed": "I do not identify Essential References Not Discussed.", "other_strengths_and_weaknesses": "## Strengths:\nIn my view, the key contributions of this paper are captured by Theorems 4.3 and 4.4. Specifically, Theorem 4.3 establishes a non-asymptotic upper bound, while Theorem 4.4 provides a corresponding lower bound, which is particularly valuable as it matches the upper bound of Theorem 4.3, albeit in a worst-case scenario.\n\n\n## Weaknesses:\n1. The motivation behind introducing linear constraints is not sufficiently clear. Although the authors provide an illustrative example concerning clinical trials, this example lacks detailed specifics to fully justify the necessity and relevance of incorporating linear constraints.\n2. The practical applicability of the proposed algorithms appears significantly limited regarding the parameter $\\delta$. According to Theorem 4.3, the algorithm is guaranteed to be $\\delta$-correct only when $\\delta < d^2/5^d$. For instance, setting $d=10$ imposes a condition $\\delta < 10^{-5}$, severely restricting the range of realistic scenarios where this method could be applied effectively.\n3. Within the main text, there is a noticeable absence of theoretical analysis specifically addressing the cPSI performance of the proposed algorithm. It would be beneficial to clarify whether the presented algorithm achieves near-optimality in terms of cPSI, or it needs a significant modification on the proposed algorithm to adapt the task of cPSI.", "other_comments_or_suggestions": "Line 85: Algorithm XX is a typo to be fixed.", "questions_for_authors": "1. In Section 5, the authors propose a two-stage algorithm comprising feasible set identification and Pareto set identification. How is the confidence level $\\delta$ configured in each of these two stages? Additionally, is historical data from the first stage utilized in the second stage?\n\n2. Could the authors clarify the meaning of the phrase \"until a correct set is identified with high probability\" in the context of the baseline method labeled \"Uniform\"?\n\n3. The authors state that the experiments depicted in Figure 4 were run 500 times. Could they also report how many times the agent succeeded in achieving e-cPSI, and whether this empirical success rate aligns with the theoretical confidence level of $\\delta = 0.1$? Furthermore, for a fair comparison, are the failure rates approximately consistent across different algorithms?\n\n4. What is the precise relationship between $T^*_{\\mathcal{M}}$ and $C^*_{\\mathcal{M}}$ in the worst-case scenario discussed in Theorem 4.4?\n\n5. What is the computational complexity of the proposed algorithm?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper investigates bandit Pareto set identification problems under constraints, where each arm corresponds to a distribution in $\mathbb{R}^d$. The goal is to identify the set of Pareto-optimal arms whose mean vectors lie within a known polyhedron. The authors study this problem in the fixed-confidence setting, deriving an instance-specific lower bound on the sample complexity and proposing near-optimal, computationally efficient algorithms. They also present numerical experiments inspired by real-world data.

The techniques used in the paper are fairly standard, but the reviewers are generally positive. The authors have adequately addressed all concerns raised during the discussion phase.

The paper could be further improved by enhancing the motivation in the introduction—for example, clarifying the significance of the problem and explaining the relevance of using polyhedral constraints.
Decision: Accept (poster)