Adaptive Algorithms for Relaxed Pareto Set Identification
Authors: Cyrille Kone
Emilie Kaufmann
Laura Richert
Venue: NeurIPS 2023 poster (2023)
Keywords: bandit
pure-exploration
pareto front
pareto set
TL;DR: In this paper we propose an algorithm which can be coupled with different stopping rules to identify the whole Pareto set or a relevant subset of optimal arms in a bandit setting.

Abstract: In this paper we revisit the fixed-confidence identification of the Pareto optimal set in a multi-objective multi-armed bandit model. As the sample complexity to identify the exact Pareto set can be very large, a relaxation allowing to output some additional near-optimal arms has been studied. In this work we also tackle alternative relaxations that allow instead to identify a relevant \emph{subset} of the Pareto set. Notably, we propose a single sampling strategy, called Adaptive Pareto Exploration, that can be used in conjunction with different stopping rules to take into account different relaxations of the Pareto Set Identification problem. We analyze the sample complexity of these different combinations, quantifying in particular the reduction in sample complexity that occurs when one seeks to identify at most $k$ Pareto optimal arms. We showcase the good practical performance of Adaptive Pareto Exploration on a real-world scenario, in which we adaptively explore several vaccination strategies against Covid-19 in order to find the optimal ones when multiple immunogenicity criteria are taken into account.

Adaptive Algorithms for Relaxed Pareto Set Identification
Cyrille Kone'
Emilie Kaufmann' emilie. -ille fr
cyrille. kone@inria.fr
Laura Richert
laura. siuuraaricchetuu-bbooeee borettt-oodduuuu..ee fr
Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9198-CRIStAL, F-59000 Lille, France Univ. Bordeaux, Inserm, Inria, BPH, U1219, Sistm, F-33000 Bordeaux, France
Abstract
In this paper revisit the fixed-confidence identification of the Pareto optimal set in a multi-objective multi-armed bandit model. As the sample complexity to identify the exact Pareto set be very large, relaxation allowing to output some additional near-optimal arms has been studied. In this work we also tackle alternative relaxations that allow instead identify relevant subset of the Pareto set. Notably, we propose a single sampling strategy, called Adaptive Pareto Explo- ration, that can be used in conjunction with different stopping rules to take into account different relaxations of the Pareto Set Identification problem. We analyze the sample complexity of these different combinations, quantifying in particular the reduction in sample complexity that occurs when one seeks to identify at most & Pareto optimal arms. We showcase the good practical performance of Adaptive Pareto Exploration on a real-world scenario, in which we adaptively explore several vaccination strategies against Covid-19 order to find the optimal ones when multiple immunogenicity criteria are taken into account.
1 Introduction
In a multi-armed bandit model, an agent sequentially collects samples from several unknown distri- butions, called arms, in order to learn about these distributions (pure exploration), possibly under the constraint to maximize the samples collected, viewed as rewards (regret minimization). These objectives have been extensively studied for different types of univariate arms distributions [2I]. In this paper, we consider the less common setting in which arms are multi-variate distributions. We interested in the Pareto Set Identification (PSI) problem. In this pure exploration problem, the agent seeks to identify the arms that are (Pareto) optimal, i.e. such that their expected values for all objectives are not uniformly worse than those of another
We formalize this as a fixed-confidence identification problem: in each round the agent selects an arm A; using an adaptive sampling rule and observes sample X, E IR from the associated distribution.
It further uses an adaptive stopping rule decide when to stop sampling and output a set of arms Š, which is her guess for (an approximation of) the true Pareto set S* Given a risk parameter 8 E (0, 1). this guess should be correct with high probability, e.g. satisfy P(Š, S*) > 1 - 8 for exact Pareto set identification, while requiring a small sample complexity т. This generalizes the well-studied fixed-come confidence Best Arm Identification (BAI) problem 15 10) to multiple objectives.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Our motivation to study multi-objectivv adaptive identification stems from the design of adaptive early- phase clinical trials. In phase I/II trials, the effects of a molecule in humans are explored, and several biological endpoinns may be assessed at the same time as indicative markers of efficacy. In particular, in the context of vaccine development, early-phase trials usually assess multiple immunogenicity endpoints (i.e. various markers of the effects of the vaccine on the immune system, such as different facets of antibody responses or other immune parameters). In the absence of a known correlate of protection during early clinical development, these endpoints may not have clear priori hierarchy, may not all be correlated, which makes an examination of the Pareto set of different vaccinal strategies particularly relevant. In addition, given the availability of various vaccine platforms (such as mRNA vaccines, viral-vector vaccines, protein vaccines), as exemplified by Covid- 19 vaccines, there may be a need to adaptively screen the various resulting vaccine strategies to select the most promising ones. Apart from clinical trials, active Pareto Set Identification can be meaningful in many real-word contexts, and we refer the reader to the various examples given by (28). such in hardware or software design. Other applications include A/B/n testing for marketing or online recommender systems in which it is common jointly optimize multiple (possibly conflicting) objectives such as user behavioral metrics (e.g. clicks, streams, dwell time, etc), supplier exposure objectives (e.g. diversity) and platform centric objectives (e.g. promotions)
For many applications, the sample complexity of exact PSI can be prohibitive, either when there are many close to optimal arms or when the Pareto set is very large, and different relaxations have been considered in the literature [4] 277. Going back to our motivation, in an adaptive trial that aims at pre-selecting certain number of treatments or vaccine strategies for further investigations in clinical trials, practical constraints (the cost and feasibility of the trials) impose a constraint on the maximal number of interesting arms that can be identified. This motivates the introduction of new setting where the agent is asked to identify at most & Pareto optimal arms. Interestingly the sampling rule that we propose for this setting can be used to solve (some generalizations of) other relaxations considered in the literature.
Related work The work most closely related to ours is that of Auer et al. who propose a relaxation, which we refer to e -PSI: their algorithm returns set S that contains w.h.p. all the Pareto optimal arms and possibly some sub-optimal arms, which when increased by e1 coordinate- wise become Pareto optimal. For arms that have sub- -ab-Gaussian marginals, they provide an instance- dependent sample complexity bound scaling with some notion of sub-optimality gap for each arm. studies structured variant of fixed-confidence PSI in which the means are regular functions of arms' descriptors. They use Gaussian process modeling and obtain worse-case sample complexity bounds. In particular 27 considers the identification of E-cover of the Pareto set, which is a representative subset of the (s)-Pareto set that will be related to our (21, criterion. The algorithms of 4 and those of 28 pr in the unstructured setting have the same flavor: they sample uniformly from a set of active arms and remove arms that have been found sub-optimal (or not representative). Auer et al. [4] further adds acceptation mechanism to stop sampling some of the arms that have been found (nearly-Joptimal and are guaranteed not to dominate an arm of the active set. In this paper. we propose instead a more adaptive exploration strategy, which departs from such accept/reject mechanisms and is suited for different types of relaxation, including our novel k-relaxation.
The work of Zaluaga et al. P p
Adaptive Pareto Exploration (APE) leverages confidence intervals on the differences of arms' coor- dinates in order to identify a single arm to explore, in the spirit of the LUCB [155] or UGapEc [ algorithms for Top-m identification in (one-dimensional) bandit models. These algorithms have been found out to be preferable in practice to their competitors based on uniform sampling and eliminations 11 an observation that will carry over to APE. Besides the miltti-dmmensonall observations, we emphasize that a major challenge of the PSI problem with respect to e.g. Top m identification is that the number of arms to identify is not known in advance. Morcover, when relaxations are considered, there are multiple correct answers. In the one- me-dimensional settings, finding optimal algorithms in the presence of multiple correct answers is notoriously hard as discussed by the authors of (5), and their lower-bound based approach becomes impractical in our maltti-dimensional setting. Finally, remark that the k-relaxation can be viewed as an extension of the problem of identifying any k-sized subset out of the best m arms in a standard bandit 2
PAL relies on confidence intervals that follow from Gaussian process regression, but can also be instantiated with simpler struutuctdred confidence intervals as those used in work and in Auer's

---

Beyond Pareto set identification, other interesting multi multi-objective bandit identification problems have been studied in the literature. For example G propose an algorithm to identify some particular arms in the Pareto set through scalarization technique 23 'he idea is to turn the multi-objecctvv pure-exploration problem into a single-objective one (unique optimal arm) by using a real-valued preference function which is only maximized by Pareto optimal arms (see e.g [2]] for some examples of these functions). In practice, a family of those functions can be used to identify many arms of the Pareto set but it is not always possible to identify the entire Pareto set using this technique (see e.g 7 for weighted sum with a family of weights vectors). In a different direction, the authors of [66 introduce the feasible arm identification problem, in which the goal is to identify the set of arms whose mean vectors belong to a known polyhedron P C R P_ In a follow up work [[7], they propose fixed-confidence algorithm for finding feasible arms that further maximize a given weighted sum of the objectives. In clinical trials, this could be used to find treatments maximizing efficacy (or a weighted sum of different efficacy indicators), under the constraint that the toxicity remains below threshold. However, in the presence of multiple indicators of biological efficacy, choosing the weights may be difficult, and examination of the Pareto set could be more suitable. Finally, some papers consider extensions of the Pareto optimality condition. The authors of [ tackle the identification of the set of non-dominated arms of any partial order defined by an R D polyhedral ordering cone (the usual Pareto dominance corresponds to using the cone defined by the positive orthant IR4"). and they provide worst-case sample complexity in the PAC setting. The work of B studies the identification of the set of non- -onnomnidteed elements in a partially ordered set under the dueling bandit setting, in which the observations consists in pairwise comparison between arms.
Outline and contributions First, we formalize in Section 2 different relaxations of the PSI problem: E ESPP as introduced by 4. 1 E2-I,,, of which a particular case was studied by 27 and CyPSSI- a novel relaxation that takes as input an upper bound & on the maximum number of -opttia arms that can be returned. Then, we introduce in Section 3 Adaptive Pareto Exploration, simple, adaptive sampling rule which can simultaneously tackle all three relaxations, when coupled with an appropriate stopping rule that we define for each of them. In Section 4 we prove upper bounds on the sample complexity of APE under different stopping rules. For E ESIP our bound slightly improves upon the state-of-the-arg Our strongest result is the bound for é --PSI--, which leads to a new notion of sub-optimality gap, quantifying the reduction in sample complexity that is obtained. Then, Section 5 presents the result of numerical study synthetic datasets, of them being inspired by a Covid-19 vaccine clinical trial. It showcases the good empirical performance of APE compared to existing algorithms, and illustrates the impact of the different relaxations.
2 Problem Setting
In this section, we introduce the Pareto Set Identification (PSI) problem and its relaxations. Fix K, E N Let V/...., 1/K be distributions over Rd with means pI..... MK E R.. Let A := [K] (1 (1...., K) denote the set of arms. Let v (- vK) and X (111 px). We use boldfaced symbols for IR elements. Letting X E RR, u E R. for any d (1...., D). X denotes the d-th coordinate of X and X + u == (X + +u.... uu..., ... + u). In the sequel, we will assume that PK have 1-subgaussian marginals B
, PK
Definition 1. Given two arms i, E A,, is weakly (Pareto) dominated by j (denoted by p S {. if for any d E (1....,D) D}, p S urz The arm is (Pareto) dominated by j (14: 3 M4 or 1) ifi is weakly dominated by and there exists d E (1..... D) such that pu < p The arm i is strictly (Pareto) dominated by j (14- - P1 or (() if for any d E (1...., D), 1 < 19.
For IRQ, the e-Pareto set (2) is the set of e-Pareto optimal arms, that is: (A') = (i E A s.t Aj E A 14, + < 1t
In particular, Si is called the Pareto sei and we will simply write S* to denote (A)) When it is clear from the context, we write St (or St)) to denote St (*Xx (or S (2)).. By abuse of notation we write St when E E R to denote St, with e == (E....,
In each round t. 1, 2, ..... the agent chooses an arm A, and observes an independent draw X, VA, with E(XA,) = A, We denote by F, the law of the stochastic process (Xt) and by Ey the
A random variable X is a -ubbgaussii if for any X E R. E(exp(A(X -[(X)) S exp( 2222)
3

---

expectation under Py. Let x Xi) the o-algebra representing the history of the process. An algorithm for PSI consists i) a sampling rule which determines which arm to sample at time based on history up to time L 1, ii) a stopping rule т which is stopping time w.r.t the filtration (Ft))21 and iii) recommendation rule which is meaesuuualll random set S, representing the guess of the learner. The goal of the learner is to make a correct guess with high probability, using few samples as possible. Before formalizing this, introduce the different notion of correctness considered in this work, depending on parameters Ei 2, 2, 2 and E [K]. Our first criterion is the one considered by 4
Definition 2. $ C A is correct for E1 if S C C St
To introduce our second criterion, we need the following definition.
Definition 3. Let E E2 2 0. subset C. Pa is an (2)=-v)cove of the Pareto set if: S C St and for any i & either $S* or 3j E such that μ4; - p. + 82.
The E-accurate set of 27 is a particular case of (E1, -ooer for which E1 = Eg E. Allowing E1 # E2 generalizes the notion of e-correct set and can be useful, e.g., in scenarios when want to identify the exact Pareto set (setting E = 0) but allow some optimal arms to be discarded they are too close (parameterized by 62) another optimal arm already returned. We note however that the sparse cover of [4) is an (s, c)cove with and additional condition that the arms in the returned set should not be too close to each over. Identifying a sparse cover from samples requires in partieular to identify S hence it can not be seen as a relaxation of E -PSI.
Definition 4. S C Pa is correct for (51, it is an (51, 62) of the Pareto set.
Definition $ C A is correct for E1-PSI-k if either i) [$]= and $ c S or ii) |3| and S* $ S holds.
Given specified objective (PSI, (E E2) E -PS--)),, and target risk parameter 8 E (0. 1). the goal of the agent is to build 8-correct algorithm, that is to guarantee that with probability larger than 1 - 8. her guess S- is correct for the given objective, while minimizing the number of samples needed make the guess, called the sample complexity.
We now introduce two important quantities to characterize the (Pareto) optimality or sub-optimality of the arms. For any two arms i, we let
m(i.j) = min (1)) m1)), and M(i.j) == max (14 13d3D
ISd3D (1)))
which have the following interpretation. If 3 m(i,j) is the minimal quantity 0 that should be added component-wist to μr so that μ4; + a A M4 a = (a...., ax.. Moreover, m(i,j) > if and only if < j. Then, for any arms i,j, if A j. M(i,j) is the minimum quantity a' such i S M4 + a', a' := (a'...., a'). a'). We remark that M), if and only if j. Our algorithms,
presented in the next section, rely on confidence intervals on these quantities.
3 Adaptive Pareto Exploration
We describe in this section our sampling rule, Adaptive Pareto Exploration, and present three stopping and recommendation rules which it can be combined solve each of the proposed relaxation. Let (t) == Σ 1(A, k) be the number of times arm & has been pulled up to round and ())() Tu Ta ( XI.. the empirical mean of this arm at time I, where X denotes the s-th observation drawn i.i.d from vg. For any arms i, E As, we let
m(i.j.t) = mi (in (t)) and M(i.j.t) = (a) -ng(t)
The empirical Pareto set is defined as
S(t)
(ieA: eje:jjeeii A,(1) - (t)(
(iEA: Vj (i).

---

3.1 Generic algorithm(s)
Adaptive Pareto Exploration relies on a lowerlupper confidence bound approach, similar to single- objective BAI algorithms like UGapEe [2] LUCB[15 and LUCB++ [26]. These three algorithms identify in each round two contentious arms: by: a current guess for the optimal arm (defined as the empirical best arm or the arm with the smallest upper bound on its sub-optimality gap), cz contender of this arm; the arm which is the most likely to outperform be (in all three algorithms, is the arm with the largest upper confidence bound in (K](())) }). Then, either both arms pulled (LUCB, LUCB++) or the least explored among b, and ct is pulled (UGapEc), The originality of our sampling rule lies in how to appropriately define b, and C₁ for the multi-objective setting. To define those, we suppose that there exists confidence intervals [L, (t, 5), Ur, (t, 5)] on the difference of expected values for each pair of arms (i. and each objective d E D, such that introducing
K MUU (4, S 14 - 14 S (1,(1,))) (1,8)) and & E= E=N &
D
& =
jiid=1
we have P(E) 2 1 8. Concrete choices of these confidence intervals will be discussed in Section 3.2 To ease the notation, we drop the dependency in 5 in the confidence intervals and further define
M (1,5,) == max (1) and (+,i.,)) == max (1) d
(2)
m (1,5,1) = (i,,i) and m mi,ji,))= =- M (1,1,))
(3)
Lemma For any round 2 1. if & holds, then for any i.j E A. M (1.j.t) S M(i.))
(i.j,t) and m ji.j.t) t) S m(i.j) S mn (i.
Noting that St = (i E A Vj + M(i,j) + 0), we define the following set of arms that are likely to be Pareto optimal:
OPT
= :-= Wi
(1...) + + 00.
Sampling rule In round I, Adaptive Pareto Exploration samples a, the least pulled arm among two candidate arms and e given by
b := argmax min 1 (i.j,, OER J32
C = argmin M (b,, jyb
The intuition for their definition is the following. Letting i be a fixed arm, note that M(i.j) > 0 for some j, if and only if there exists a component d such that na > n i.e i is not dominated by Moreover, the larger j). the more is non-dominated by j in the sense that there exists d such that m >> un. Therefore, i is strictly optimal if and only if for all j # i, M(i.j) > 0 i.e a == min ب M(i.j) > O. And the larger ag, the more i looks optimal in the sense that for each arm j * i, there exists component d, for which i way better than j. the a; are unknown, we define by as the maximizer of an optimistic estimate of the o; ss. We further restrict the maximization to arms for which we are not already convinced that they are optimal (by Lemma the arms in OPTs: (t) are (nearly) Pareto optimal on the event E). Then, we note that for tixed arm i, M(i.j) < 0 if and only if is strictly dominated by j. And the smaller M(i,j), the more j is close to dominate (or largely dominates it): for any component d, nu 2 small (or negative). Thus, for a fixed arm i, argmingz4 Mii,j) can be seen as the arm which is the closest dominate i (or which dominates by the largest margin). By minimizing lower confidence bound on the unknown quantity M(b,, j). our contender c, can be interpreted as the arm which is the most likely to be (close to) dominating by. Gathering information on both b, and c can be useful to check whether can indeed be optimal.
Interestingly, we show Appendix E that for = 1, our sampling rule is close but not identical to the sampling rules used by existing confidence-basse best arm identification algorithms.
5

---

Stopping condition
Recommendation
Objective
Ten
(t)
> 0 A (t'
T
E1-PSI
Tei
2
(t)
0 A Z 0t>0
OPT Te
(21,52)-PS)
[PPT (t) K
OPT
Ei-PSI-k
Table 1: Stopping conditions and associated recommendation
Stopping and recommendation rule(s) Depending the objective, Adaptive Pareto Exploration can be plugged in with different stopping rules, that are summarized in Table | with their associated recommendations. To define those, we define for all A. 61, 0, ofth (1)
max m (i,5,)) e2 OPT*)()) (1) and (L) == min M (1,3,)) + JØC
and let gt) (t). Introducing
7 (t) == min
1 (t), and (t) == min max iES(1)
iES(()
for EI-PI, our stopping rule is Te, := in K Z (t) 0 ^ Z (t) 0} and the associated recommendation is O(T,,) where
O(1) = (i E S(D)= 1j ;i: m (7, ), > 0}
consists the current empirical Pareto set plus some additional arms that have not yet been formally identified as sub-optimal. Those arms should be (s1) Pareeto optimal.
For (c1, 62 3-SI define similar stopping rule Tenes, where the stopping statistics respectively replaced with
7 (1) = min max(g(²( (f), (1) and (5) = min max(g)"()) (1) (E)(1)
iES(O)
with the convention ming = +oo, and the recommendation is OPT (TE,.e.)
To tackle the -PI-k relaxation, we propose to couple Te, with an additional stopping condition checking whether OPT*1 (t) already contains l: arms. That is, we stop at -h == min (Te, r*) where 7 := it 2 K |PT (t) 2 k} with associated recommendation OPT*((>*) Depending of the reason for stopping (Te, or 7²), we follow the corresponding recommendation.
Lemma 2. Assume & holds. For EI-PSI (resp. (21, E1-PSI-k), Adaptive Pareto Exploration combined with the stopping rule Te, (resp. TeL.52 resp. T outputs a correct subset.
We decoupled the presentation of the sampling rule to that of the "sequential testing" aspect (stopping and recommendation) We could even go further and observe that multiple tests could actually be run in parallel. for free. we collect samples with APE (which only depends on E1). whenever one of the three stopping conditions given in Table I triggers, for any values of S2 or k, we can decide stop and make the corresponding recommendation or continue and wait for another "more interesting" stopping condition to be satisfied. E holds, a recommendation made at any such time will be correct for the objective associated the stopping criterion (third column in Table D
Remark 1.
3.2 Our instantiation
We propose to instantiate the algorithms with confidence interval on the difference of pair of arms. For any pair j E A, we define function Bi,5 such that for any d E [D], U. (t) (t (ttt-)-(( (t)
and , (4) ( (L) (1()) (t) We take from 20 the following confidence bonus for time-
uniform concentration:
log (L))
(t,(t):= : Ca9
Σ aEtiot
log(4 log(Ta(t)))
Σ aE(i.)
(4)
Ta(t)
where K1 K(K 1)D/2 and C s + log(x) is calibration function. They result in the simple expressions M (i. M(i + (t, (t) and m m= m(i.j,t) + (t) As an

---

Algorithm 1: EAAAPE-: Adaptive Pareto Exploration for PS-PSI
Data: parameter 81 2 0, k E [K]
initialize: sample each arm once, set / = K, TK() = 1 for any i i A for f K .,...: do
S(t) {i E R. A.
0};
OPT (t) ( E : A - te)
if TPPT (1) & then
L break and output OPT*()) (I)
if (t) > 0 Z (t) > 0 then
[ break and output (t)) = S(O S(1): : mi, - Ber(t) (0]1))
argmax, (() minjzi [M(i,,,t) + (t)
c a [Mbb.. [t);;
sample 0r = argmin (b,,, Ti());
example, we state in Algorithm ! the pscudo-code of APE combined the stopping rule suited for the k-relaxation of PPSI which we refer to E1-AP.-
In Appendix (t)(t)) = (t) (t(t) where [L,(t), U:(t) is a confidence interval on μ4; This is the approach followed by LUCB for D and prior work on Pareto identification 4 277 In practice we advocate the use of the pairwise confidence intervals defined above, even if our current analysis does not allow quantify their improvement. For the LUCB-like instantiation, we further derive in Appendix an upper bound on the expected stopping time of APE for the different stopping rules.
also study different instantiation based confidence bounds of the form
Theoretical analysis
In this section, we state our main theorem on the sample complexity of our algorithms and give a sketch of its proof.
First let us introduce some quantities that are needed state the theorem. The sample complexity of the algorithm proposed by 4 for (51 - set identification scales as sum over the arms i of 1/(A, V ) where A, called the sub-optimality gap of arm and defined as follows. For sub-optimal arm i S* (2'),
A = max m(i,j), JES
which is the smallest quantity that should be added component-wise to μ1 to make appear Pareto optimal w.r. {H, E A.. For a Pareto optimal arm E (At), the definition more involved:
mminjearss A, S* := {i}
A, =
min (,55) else,
where
57
min (). and 67:= := min {(M(j. 1)) + A,}. \e)
jEAYS-
For E R, (x)+ max (ar, 0). We also introduce some additional notion needed express the contribution of the k-relaxation. Let < k < K. For any arm i, let w; = mingzi M(i.j) and define
max
S*. = argmaa Wi,
1...k
VEA
with the k-th max and first to k-th argmax operators. Observe that w > 0 if and only if (((()) 2 k. Theorem 1. Fix risk parameter å (0, e1 2 let S K and v bandit with 1-subgaussian marginals. With probability at least 1 5, -1-APE-k recommends correct set for the -PSPSi
objective and stops after at most
Σ
88
log
2K(K 1)D log
12c
A
A
samples, where for each E A. A = max (
7

---

First, when k = K, observing that E1-APE-K K provides a ô-correct algorithm for E1-PSI, our bound improves the result of for the - problem terms of constant multiplicative factors and log log A-1 terms instead of log 2- It nearly matches the lower bound of Auer et al. [.] for the EPPPSI problem (Theorem 17 therein). sample complexity. In particular, we can remark that for any arm i E S* max (ox wx) wk- Intuitively, it says that we shouldn't pay more than the cost of identifying the k-th optimal arm, ordered by the w/s. A similar result has been obtained for the any k-sized subset of the best m problem (25]. But the authors have shown the relaxation only for the best m arms while our result shows that even the sub-optimal arms should be sampled less.
also shows the impact of the k-relaxation on the
In Appendix D we prove the following lower bound showing that in some scenarios, S1-APE-k is optimal for E -PPSI- up to D log K) and constant multiplicative terms. We note that for e a lower bound featuring the gaps Aa and ει was already derived by Auer al. 4
Theorem 2. There exists a bundit instance v with | p 22 any 8-correct algorithm for O-PSI-k verifies
3 such that for t E {p.P 1,p 2}
K
1
(Ta) 2 D
log
Σ
where D = Da + wh and Ta the stopping time of the algorithm.
C we prove that Theorem without the wh terms also holds for (#1, e2)-EE This does not justiñies the reduction in sample complexity when setting E2 > 0 (21, observed in our experiments but it at least guarantees that the Eg-relaxation doesn't 't make things worse
In Appendix
Furthermore, since our algorithm allows E O, it is also algorithm for BAI when D = 1, 0.
We prove in Appendix that in this case, the gaps A matches the classical gaps in BAI 2 18 and derive its sample complexity from Theorem I showing that it is similar in theory to UGap ( LUCB [6] and LUCB++ [26] but have better empirical performance.
Sketch of proof of Theorem Using Proposition 24 of 220 in 4 yields P 2 for the good event defined in ①..
we first prove that the choice of Br,; Combining this result with Lemma 2
yields that A1-APE- is correct with probability at least 1 - 0.
The idea of the remaining proof is to show that under the event E, if APE has not stopped at the end of round f, then the selected arm a has not been explored enough. The first lemma showing this is specific to the stopping rule z used for PSI-K..
Lemma 3. Let 81 2 and E [K] & holds and < T.k then w < 28 (t)-
The next two lemmas are more general as they apply to different stopping rules.
Lemma 4. Let E1 2 Let - for some k E [K] or Tei,es for some E2 2 If holds and 1 < then Aa, S 2, (t).
Lemma 5. Let 2 0 and T be as in Lemma If &e holds and t < then a.
As can be seen in Appendix B the proofs of these three lemmas heavily rely on the specific definition of b, and e. In particular, to prove Lemma [ we first establish that when < any arm j e A satisfies m (bb., j. t) S 3 (t). The most sophisticated proof then that of Lemma which relies on a case distinction based on whether b,
belongs to the set of optimal arms.
These lemmas permit to show that, on & if < + then Ka, < 28a (1) & 1,, where we define 8d to be the expression of (t) when (,(t) = (t) = n. Then we have
118)
ΣΣ
1( (a.
1
(a =
S. s 23
Σ
inf n 2 2: A. 2.8h)
(5)
RER
A careful upper-bounding of the RHS of 5 completes the proof of Theorem
8

---

5 Experiments
We evaluate the performance of Adaptive Pareto Exploration on real-world scenario and on synthetic random Bernoulli instances. For a fair comparison, Algorithm of 4] referred to as PSI-Unif-Elin and APE are both run with our confidence bonuses Big on pairs of arms, which considerably improve single-arm confidence bonuse As anytime confidence bounds are known to be conservative, we use K1 = 1 in f instead of its theoretical value coming from a union bound. Still, in all our experiments, the empirical error probability was (significantly) smaller than the target d 0.1.
Real-world dataset COV-BOOST [24 is phase 2 trial which was conducted on 2883 participants
to measure the immunogenicity of different Covid-19 vaccines as third dose (booster) in various combinations of initially received vaccines (first two doses). This resulted in total of 20 vaccination strategies being assessed, each of them defined by the vaccines received as first, second and third dose. The authors have reported the average responses induced by each candidate strategy on cohorts of participants, measuring several immunogenicity markers. From this study, we extract and process the average response of each strategy to 3 specific immunogenicity indicators: two markers of antibody response and one of the cellular response. The outcomes are assumed to have a log-normal distribution (24). We use the average (log) outcomes and their variances to simulate a multivariate Gaussian bandit with K = 20, D 3. We give in Appendix H.2 some additional details about the processing of the data, and report the means and variances of each arm. In Appendix H.T we further explain how APE can be simply adapted when the marginals distributions of the arms have different variances. In this experiment, we set $ 0, 8 = 0.1 and compare PSI-Unif-Elim to 0-APE-k (called
1.
4.5
4.2
0.8
APSN-11
APEjoo
PS:UMEE
7.5
8.0
35
9.0
9.5
10.0
125
at8-sppo bo
Figure 1: On the left is the log of the empirical sample complexity of PSI-Unif- Cil-unif-Elim and APE on the real-world scenario plot (right) for out of the 3 immunogenicity indicators.
APE-k in the sequel) for different values of k. The empirical distribution of the sample complexity of the algorithms, averaged over 2000 independent runs, are reported in Figure The results are shown in log-scale (y-axis is the log of the sample complexity) to fit in the same figure. As |S*| = 2, we first observe that, without the relaxation (i.e. for k > 3), APE outperforms its state-of-the-art competitor PSI-Unif-Elim Moreover for = 1 or = 2, the sample complexity of APE-k is significantly reduced. For A = 2 when the stopping time r is reached some sub-optimal arms have possibly not yet been identified as such, while for = 3. even if the optimal arms have been identified, the remaining arms have to be sampled enough to ensure that they sub-optimal before stopping. This explains the gap in sample complexity between & = 2 and k 3. In Appendix H3 we compare APE to an adaptation of PSI-Unif-Elim for the k-relaxation, showing that APE is always preferable.
Experiments on random instances To further illustrate the impact of the k-relaxation and to strengthen the comparison with PSI-Unif-Elin generated multi-variate Bernoulli instances, with K = 5 arms and different values of the dimension D. We set d 0.1 and E 0.005 (to have reasonable rumning time). The averaged sample We observe that APE (with & = K) uses 20 to 25% less samples
the previous algorithms 2000 randomly
complexities are reported in Table 2
In their experiments.
4 already proposed the heuristic use of confidence bonuses of this form

---

than SI--Unif-Elim and tends to be more efficient as the dimension increases (and likely the size of the Pareto set, since the instances are randomly generated). We also note that identifying k-sized subset of the Pareto set requires considerably less samples than exact PSI. In Appendix H.3 we also provide examples of instances for which APE takes up to times less samples than UnI-Unif-FR
S1-APE1
E1-APE-2
61-APE-3
E1-APE-4
E1-APE-5
E1 Ei-PSI-Unif--lim
D D - 4 214
811
39530
109020
145777
150844
190625
6410
19908
68061
124001
157584
= 8 119
204
405
1448
20336
27270
Table 2: Average sample complexity over 2000 random Bernoulli instances with K arms. On
average the size of the Pareto set was (2.295, 4.0625, 4.931) respectively for the dimensions 2, 4, 8.
To illustrate the impact of the 22 relaxation, setting ε we report the sample complexity of APE associated with the stopping time Tu,ea for 20 equally spaced values of E2 [0.01, 0.05], averaged over 2000 random Bernoulli instances. Figure 2 shows the decrease of the average sample complexity when E2 increases (left) and the average ratio of the size of the returned set to the size of the Pareto set (right). Note that for E 0, we have (TTo.ea) C The average sample complexity reported decreases up to 86% for the instance with K 5.
D = 2 while the returned set contains more than
90% of the Pareto optimal arms. In Appendix
H.3
we further illustrate the behavior of APE with the
E2 relaxation on fixed instance in dimension 2.
Instanee tpp
X- 0
X- 5,66
0.94
20000
009
0.07
0.8
20030
10030
0010
0015
0.000
0.25
003:
8.05
2.40
0.44
0.000
9210
0.91
5.000
0.05
0.030
0.005
3940
0045
0.000
(a) Average sample complexity vs 82
(b) Average ratio 10(ro.eg 1/1151 VS 82
Figure 2: APE with Tu,e2 averaged over 2000 random Bernoulli instance with K arms
6 Conclusion and perspective
We proposed and analyzed APE, an adaptive sampling rule in multi-variate bandits models that when coupled with different stopping rules can tackle different relaxations of the fixed-confidence Pareto Set Identification problem. Our experiments revealed the good performance of the resulting algorithms compared to the state-of-the-art PSI algorithm as well as the great reductions in sample complexity brought by the relaxations. In future work, we intend make our algorithms more practical for possible applications to clinical trials. For this purpose, as measuring efficacy takes time, we will investigate its adaptation to a batch setting, following, e.g. the work of [13] for BAI We will also investigate the use of APE beyond the fixed-confidence setting, to the possibly more realistic fixed-budget 2 or anytime exploration
[14] settings. To the best of our knowledge, no algorithm exists in the literature for PSI in such settings. Finally, following the works of [28 A. we defined the ,1,82 82 relaxations with scalar values, so that the same slack applies to all components. Although we could easily modify our algorithms to tackle vectorial values 1 E2, so far we could only prove dependence on min, ef in the sample complexity. We intend to study the right quantification in the sample complexity when E and E2 are vectorial.
10

---

Acknowledgments and Disclosure of Funding
Cyrille Kone is funded by Inria/Inserm PhD grant. Emilie Kaufmann acknowledges the support of the French National Research Agency under the projects BOLD (ANR-19-CE23--006---) and FATE (ANR22-CCE23-016-00))
References
[1] C. Ararat and C. Tekin. Vector optimization with stochastic bandit feedback. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206, pages 2165-2190. PMLR, 2023.
[2] J.-Y. Audibert and S. Bubeck. Best arm identification in multi-armed bandits. In COLT 23thh Conference on Learning Theory- - 2010, page 13 p.. 2010.
[3] J. Audiffren and L.. Ralaivola. Bandits dueling on partially ordered sets. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[4] P. Auer, C.-K. Chiang, R. Ortner, and M.-M. Drugan. Pareto front identification from stochastic bandit feedback. In Proceedings of the 19th International Conference Artificial Intelligence and Statistics, volume 51, pages 139-997.. PMLR, 2016.
[5] R. Degenne and W.M. Koolen. Pure exploration with multiple correct answers. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[6] M.-M. Drugan and A. Nowe. Designing multi-objective multi-armed bandits algorithms: A study, In The 2013 International Joint Conference Neural Networks (IJCNN) pages 1-8, 2013.
[7] M. Ehrgott. Multicriteria Optimization. Springer, second edition edition, 2005.
[8] E. Evrn-Dar, S. Mannor, and Y. Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 1079 105, 2006.
[9] V. Gabillon, M. Ghavamzadeh, and A. Lazaric. Best arm identification: A unified approach to fixed budget and fixed confidence. In Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
[10] A. Garivier and E. Kaufmann. Optimal best arm identification with fixed confidence. In 29th Annual Conference on Learning Theory, volume 49, pages 998-1027. PMLR, 2016
[11] K. Jamieson, M. Malloy, R. Nowak, and Bubeck. lil' ucb An optimal exploration algorithm for multi-armed bandits. In Proceedings of The 27th Conference Learning Theory, volume 35, pages 423-439, PMLR, 2014.
[12] M. Jourdan, R. Degenne, D. Baudry, R. de Heide, and E. Kaufmann. Top two algorithms revisited. In Advances in Neural Information Processing Systems, volume 35, pages 26791- 26803. Curran Associates, Inc., 2022.
[13] K.-S. Jun, K. Jamicson, R. Nowak, and X. Zhu. Top arm identification in multi-armed ban- dits with batch arm pulls. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51, pages 148. PMLR, 2016.
[14] K-S. Jun and R. Nowak. Anytime exploration for multi-armed bandits using confidence information. In Proceedings of The 33rd International Conference on Machine Learning, volume 48, pages
PMLR, 2016.
[15] S. Kalyanakrishnan, A. Tewari, P. Auer, and Stone. PAC subset selection in stochastic multi- armed bandits. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 227-234. Omnipress, 2012.
[16] Katz-Samuels and C. Scott. Feasible arm identification. In Proceedings of the 35th Interna- tional Conference Machine Learning, volume 80, pages 2535-2543 PMLR, 2018
11

---

[17] J. Katz-Samuels and C. Scott. Top feasible arm identification. In Proceedings of the Twenty- Second International Conference on Artificial Intelligence and Statisties, pages 1593-1601. PMLR, 2019.
[18] E. Kaufmann, O. Cappé, and A. Garivier. On the complexity of best-arm identification in multi--rmmed bandit models. Journal of Machine Learning Research, 17(1):1-42, 2016.
[19] E. Kaufmann and S. Kalyanakrishnan. Information complexity in bandit subset selection. In Conference On Learning Theory, volume 30. JMLR: Workshop and Conference Proceedings, 2013.
[20] E. Kaufmann and W.-M. Koolen. Mixture martingales revisited with applications to sequential tests and confidence intervals. Journal of Machine Learning Research, 22(246))1-444 2021.
[21]
Lattimore and C. CSzepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[22] R. Mehrotra, N. Xue, and M. Lalmas. Bandit based optimization of multiple objectives on a music streaming platform. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, page 3224-32222222 3233. Association for Computing Machinery, 2020.
[23] K. Miettinen. Nonlinear multiobjective optimization. In International Series in Operations Research and Management Science, 1998.
[24] A.-P.-. Munro, L. Janani, V. Cornelius, and et al. Safety and immunogenicity of seven COVID- 19 vaccines as a third dose (booster) following two doses of ChAdOxi nCov- 19 BNT16262 in the UK
a blinded, multicentre, randomised, controlled, phase 2 trial. The
Lancet, 398(10318):2258 22722222222222222-222222222222 2021.
[25] A. Roy Chaudhuri and S. Kalyanakrishnan, PAC identification of many good arms in stochastic multi-armed bandits. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 991-1000. PMLR, 2019.
[26] M. Simchowitz, K. Jamieson, and B. Recht. The simulator: Understanding adaptive sampling in the moderate-confidened regime. In Proceedings of the 2017 Conference Learning Theory, volume 65, pages 7794-1844 PMLR, 2017.
[27] M. Zuluaga, A. Krause, and M. Püschel. e-pal: An active learning approach to the multi- objective optimization problem. Journal of Machine Learning Research, 17(14)):1-3,, 2016.
[28] M. Zuluaga, G. Sergent, A. Krause, and M. Püschel. Active learning for multi-objective optimization. In Proceedings of the 30th International Conference on Machine Learning, volume 28, pages 462-470. PMLR, 2013.
12


Reviews:
[{"review_id": "rTnaAyvvG5", "reviewer": "Reviewer_9Lr4", "summary": "This paper studies a relaxed problem of Pareto set identification, in which the learner is required to identify a subset of the optimal arms. A single sampling strategy APE is proposed and then combined with various stopping rules to realize different relaxations of the original problem. In theory, this paper derives the sample complexity of these combinations. The proposed method is also validated empirically on a real-world scenario of Covid-19 vaccination. ", "questions": "See the weaknesses.", "limitations": "Limitations have been properly discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Relaxed Pareto set identification is an important problem for multi-objective MAB. The proposed new framework may inspire new researches in this field, if properly justified.\n\n2. The proposed sampling strategy sounds novel, and the analysis is technically sound.\n\n3. The experiment on selecting vaccination strategies against Covid-19 is interesting.", "weaknesses": "1. One of the main contributions of this paper is to propose a new problem of $\\epsilon$-PSI-$k$ and provide an analysis framework for this problem. However, I think the motivation of $\\epsilon$-PSI-$k$ should be explained in more detail. I am not sure if we need this new formulation as $(\\epsilon_1,\\epsilon_2)$-PSI has already dealt with the sparsity issue. \n\n2. Some detailed explanations of the intuition of the proposed sampling strategy (and why it outperforms previous strategies in principle) may help better understand the novelty in the algorithm design. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you for your review. We address your two concerns about weaknesses below. \n\n* Our motivation for the $\\epsilon_1$-PSI-$k$-relaxation comes from possible applications to early stage clinical trials, e.g. in vaccinology as in our real-world scenario. In this context, the constraint to identify at most $k$ interesting arms that will be investigated in further phases of clinical development (phase II, phase III) comes from material constraints: the cost of producing distinct treatments at a larger scale, a maximum number of patients that has to remain an order of magnitude larger than the number of arms, etc. (see also line 47-53 in our introduction). It is true that the parameter $\\epsilon_2$ in the $(\\epsilon_1,\\epsilon_2)$-PSI relaxation also enforces some sparsity, but it provides no control on the size of the output, which is desirable in the above mentioned scenario. Thus, we view these two relaxations as two different ways of ensuring sparsity, and one of our main contribution is to propose a single exploration strategy (APE) that can tackle both objectives. Our strongest results are for $\\epsilon_1$-PSI-$k$, for which we manage to quantify the reduction in sample complexity resulting from the limitation $k$ on the size of the output, both in theory and in practice.\n\n * Regarding the novelty in algorithmic design, we emphasize that our sampling rule is the first fully sequential sampling rule ever proposed for (any of the studied relaxations of) Pareto front identification. It is fully sequential in the sense that in each round $t$, the most informative arm $a_t$ is selected in a data-dependent way. All prior algorithms are based on a ``racing'' approach, i.e. they use uniform sampling and an accept/reject mechanism. It is known in single objective bandits that fully sequential algorithms usually outperform their racing counterparts (see [9]) and we extend this observation to the multi-objective setting. Following your suggestion, we will provide a more detailed explanation of the intuition for our sampling rule, which is currently a bit shallow. It is built in the spirit of the adaptive lower/upper confidence bounds type algorithms in the single objective bandit setting, such as LUCB, LUCB++ or UGap. These three algorithms identify in each round two contentious arms: $b_t$: a current guess for the optimal arm (defined as the empirical best arm or smallest upper bound on its sub-optimality gap), $c_t$: a contender of this arm; the arm which is the most likely to outperform $b_t$ (in all three algorithms, it is the arm with the largest upper confidence bound in $[K]\\backslash \\\\{b_t\\\\}$). Then, either both arms are pulled (LUCB, LUCB++) or the least explored among $b_t$ and $c_t$ is pulled. The originality of our sampling rule lies in how to appropriately define $b_t$ and $c_t$ for the multi-objective setting. The intuition for their definition is the following. Let $i$ be a fixed arm. Note that $M(i,j)>0$ for some $j$, if and only if there exists a component $d$ such that $\\mu_i^d > \\mu_j^d$ (recall that $M(i,j):= \\max_d (\\mu_i^d - \\mu_j^d)$) i.e $i$ is not dominated by $j$. Moreover, the larger $M(i,j)$, the more $i$ is non-dominated by $j$ in the sense that there exists $d$ such that $\\mu_i^d >> \\mu_j^d$. Therefore, $i$ is strictly optimal if and only if  for all $j\\neq i$, $M(i,j)>0$ i.e $\\alpha_i:= \\min_{j\\neq i}M(i,j)>0$. And the larger $\\alpha_i$, the more $i$ looks optimal in the sense that for each arm $j\\neq i$, there exists a component $d_j$ for which $i$ is way better than $j$. As the $\\alpha_i$'s are unknown, we define $b_t$ as the maximizer of an optimistic estimate of $\\alpha_i$. We further restrict the maximization to arms for which we are not already convinced that they are optimal (by Lemma 1, the arms in $OPT^{\\varepsilon_1}(t)$ are (nearly) Pareto optimal on the event $\\mathcal{E}$). Then, we note that for a fixed arm $i$, $M(i,j) < 0$ if and only if $i$ is strictly dominated by $j$. And the smaller $M(i,j)$, the more $j$ is close to dominate $i$ (for any component $d$, $\\mu_i^d - \\mu_j^d$ is small). Thus, for a fixed arm $i$, $\\text{argmin}_{j\\neq i} M(i,j)$ can be seen as the arm which is the closest to dominate $i$ (or which dominates it by the largest margin). \n By minimizing a lower confidence bound on the unknown quantity $M(b_t,j)$, our contender $c_t$ can be interpreted as the arm which is the most likely to be (close to) dominating $b_t$. Gathering information on both $b_t$ and $c_t$ can be useful to check whether $b_t$ can indeed be optimal."}, {"review_id": "GWhMHJGxGC", "reviewer": "Reviewer_J7Kd", "summary": "This paper extends the best arm bandit problem to a multi-objective version to identify the arms that are in the Pareto front.", "questions": "In the definition of Pareto front, why we don't consider the variance of the distribution? ", "limitations": "See above", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This problem is new and the author provides a clear practice motivation of this problem.\n\nThe theory study seems valid and complete.", "weaknesses": "The math notation seems a bit over-complicated and I was wondering can you simplify it?\n\nOverall, extending the best arm bandit problem into multi-object setting seems straightforward, which limits the novelty of this paper.\n\nThe experiment result looks a bit hand-wavy. I understand that there might not be any algorithm specifically designed for such problem, but I was wondering how the proposed method compares with some naively modified baselines?\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We comment about each weakness mentioned and answer your question below.\n\n * Due to the multi-dimensional setting and the fact that we consider three relaxations simultaneously, we agree that the notation can be a bit heavy. We will double check if some simplification is possible.\n\n * While PSI (Pareto set identification) is a natural extension of the best arm identification (BAI) problem in standard bandits, PSI is actually a more challenging problem. In PSI we don't know the number of optimal arms beforehand: it can go from $1$ to $K$, while in BAI the classical assumption is that there is a single optimal arm. When relaxations are further taken into account, there are multiple valid solutions (e.g. for $\\varepsilon_1$-PSI-$k$ when the size of the Pareto set is larger than $k$, any subset of size $k$ is a valid guess), which creates some additional difficulties even in the uni-dimensional setting [10]. It is true that our sampling rule shares a common structure with that of existing adaptive BAI algorithms which rely on playing two contentious arms ($b_t$ and $c_t$ in our paper), often the empirical best arm and a contender (LUCB, UGap or more recently Top Two algorithms). However, it actually took us several iterations to come up with the right definitions for $b_t$ and $c_t$ for the PSI problem, which interestingly do not exactly coincide with the choices in prior BAI algorithms when $D=1$ (see Appendix E). You can also read our answer to reviewer 9Ln4 for a better intuition about our definition of $b_t$ and $c_t$, which will be included in our revision. As a start, in the multi-objective case we no longer have an ``empirical best arm\" but a set of arms of random size that could equally be optimal. Likewise, many results and techniques known so far for BAI do not directly apply to our setting and our analysis required specific results to pin down the behavior of our algorithm: Lemma 3 and Lemma 4. We will be happy to sketch their proof (and their crucial ingredient Lemma 8 currently stated in appendix) if we are given an extra page for our revision.\n\n* The experiments reported in the main paper are mostly meant to illustrate the reduction in sample complexity obtained when solving the $\\varepsilon_1$-PSI-$k$ relaxation (for different values of $k$), compared to the state-of-the-art algorithm for the (unrelaxed) $\\varepsilon_1$-PSI problem from [6], which we call PSI-Unif-Elim. In particular, when $k=K$ (the total number of arms), we are comparing two algorithms ($\\varepsilon_1$-APE-$K$ and PSI-Unif-Elim) designed for the same objective: $\\varepsilon_1$-PSI, showing that our proposal leads to a reduced sample complexity (by 25$\\\\%$ on average, Figure 1 and Table 2 of the main paper). In Appendix H.3.3. we further propose a naive modification of PSI-Unif-Elim for the $\\varepsilon_1$-PSI-$k$ objective (Algorithm 3) and compare it to $\\varepsilon_1$-APE-$k$. The results, reported in Figure 8 show that $\\varepsilon_1$-APE-$k$ consistently has smaller sample complexity (up to 3 times smaller). We will put more emphasis on this last finding in our revision, which is currently only briefly mentioned in l.302-303 of the main paper.\n\n * We are not sure of what you mean by ``considering the variance of the distributions in the definition of the Pareto front''. Right now, our goal (as that of prior work) is to identify the Pareto set of the set of means vectors, assuming that the marginal distributions of all objectives are sub-Gaussian with a known common bound on their sub-Gaussian parameter (l. 119-121). The setting and algorithms can be adapted to consider marginals that have different scales (i.e. different *known* bounds on their sub-Gaussian parameter), which is the case in our practical application, as explained in Appendix H.1. This amounts to identify the Pareto set of the vectors \n$\\\\{(\\mu_i^{d}/\\sigma^{d})_{d \\in [D]}\\\\}_i$ where $\\sigma^{d}$ is the sub-Gaussian parameter of criterion $d$.  But maybe what you had in mind is to consider unknown variances and possibly a risk-averse version of the PSI problem, e.g. in which the goal is to identify the Pareto set of the set  $\\\\{\\boldsymbol{\\mu}_i - \\alpha \\boldsymbol{\\sigma}_i^2\\\\}_i$  for some parameter $\\alpha > 0$, where the vector $\\boldsymbol{\\sigma}_i^{2}$ contains the variance of each objective $d$ (which could now depend on $i$ as well). Adapting our algorithm to this setting would require significant effort (e.g. building confidence intervals on unknown variances) that are beyond the scope of this paper.    "}, {"review_id": "OJinlBhRB7", "reviewer": "Reviewer_yuHu", "summary": "The primary objective of the paper is to address the challenge of identifying a set of arms, consisting of at most $k$ arms, where each arm is either Pareto optimal or close to Pareto optimal. The paper explains the concept of Pareto optimality within the context of bandit problems. To tackle this problem, the paper presents the $\\epsilon_1$-APE-$k$ (Adaptive Pareto Exploration) algorithm and establishes an upper bound on the sample complexity. Furthermore, empirical evidence is provided to demonstrate the effectiveness of the proposed algorithm.", "questions": "One potential weakness is the lack of information regarding scalability issues encountered when running large-scale experiments using the $\\epsilon_1$-APE-$k$ algorithm. It would be valuable to understand whether the algorithm faces any challenges in handling larger datasets or more complex scenarios. Additionally, providing references on the scale of parameters used in A/B testing for applications beyond COVID datasets would further strengthen the practicality of the proposed approach.\n\nAnother point to consider is the limited discussion on the broader scope of utilizing Pareto sets in various applications apart from clinical trials. Exploring and discussing other potential domains where Pareto sets could be beneficial would enhance the paper's impact and shed light on additional practical applications.", "limitations": "No limitations or potential impact of their work discussed", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "One strength of the paper is its focus on addressing the problem of Pareto optimality in bandit literature, which is an underexplored area. The paper introduces a novel problem setup and clearly defines the goals for different scenarios related to Pareto optimal identification, including the identification of Pareto optimal sets, near Pareto optimal sets, and at-most $k$ near Pareto optimal sets.\n\nThe paper excels in providing a comprehensive discussion on sample complexity upper bounds, highlighting the theoretical aspects of the problem. It also establishes connections to the existing literature on Pareto optimality in bandits, demonstrating a solid understanding of the research landscape.\n\nFurthermore, the paper offers ample experimental evidence to support its claims, including experiments conducted on real-world datasets. This empirical validation strengthens the credibility of the proposed approaches and enhances the practical relevance of the research.", "weaknesses": "One weakness of the paper is the absence of references to real-world applications that could benefit from the proposed framework. For instance, discussing potential applications such as A/B testing in clinical trials would enhance the practical relevance and broader impact of the research.\n\nAnother weakness is the lack of discussion of lower bounds in the main paper. Given that the problem setup for Pareto set identification is relatively new, it would be valuable to explore more properties of the lower bounds to gain insights into the tightness of the derived upper bounds. This would provide a more comprehensive understanding of the problem and its inherent complexities.\n\nThe paper lacks a thorough discussion on the computational complexity of the $\\epsilon_1$-APE-$k$ algorithm. Considering the importance of computational efficiency in practical applications, it would be beneficial to address", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We address your concerns and answer your questions below.\n\n* We will add a paragraph about the computational complexity of $\\varepsilon_1$-APE-$k$ in Section 5, with some details in Appendix H. The time complexity of $\\varepsilon_1$-APE-$k$ is $\\mathcal{O}(K^2D)$ and its memory complexity is $\\mathcal{O}(K^2)$. The computational bottleneck is the computation of the $M(i,j,t)$ for each $(i,j) \\in [K] \\times [K]$, which requires a triple-nested for-loop over $[K]\\times [K]\\times[D]$). We have implemented the algorithm in C++17 compiled with GCC12. To give an idea of the run time, a single run on a random Bernoulli instance with $K=1000, D=10$ takes around 4 minutes for $0.1-$APE-$1000$ on a personal computer (a single 3GHz ARM core used, 8 GB RAM, 256 GB disk storage) with $\\delta=0.01$ and no particular optimization. We are aware that due its fully sequential nature, our algorithm may have a higher computational cost compared to uniform sampling strategies which typically proceed in batches. However, in our implementation the most time-consuming operation was actually collecting a sample from the selected arm(s), especially for multivariate Gaussians. So that finally, in the experiments, our algorithm which ultimately requires less samples had in practice a smaller computational cost compared to PSI-Unif-Elim which uses uniform sampling.  \n \n* We will provide in our revision more examples of practical cases in which adaptively identifying a Pareto set is meaningful. In the current version of the introduction we mostly focused on the motivating examples used in our experimental evaluation, for which the $k$-relaxation is especially relevant, referring only briefly to other examples contained in [5] (see l.42-44). We will elaborate on those and provide others. For example in [5] the authors have evaluated the PAL (Gaussian Process based) algorithm on the SW-LLVM dataset, which is a dataset of 1023 compiler settings and 11 objective indicators (memory footprint, performance etc.). Since it is unlikely that a single compiler setting optimizes all the 11 objectives, it is meaningful to find compiler settings that are Pareto optimal. Another application is hardware design optimization [5,7]. The idea is similar to software design but the arms are different hardware implementations designed to solve a given problem. The usual objectives for this application include chip area, throughput, energy consumption and runtime.   \nOther applications include A/B/n testing for marketing or online recommender systems in which it is common to jointly optimize multiple (possibly conflicting) objectives such as user behavioral metrics (e.g. clicks, streams, dwell time, etc), supplier exposure objectives (e.g. diversity) and platform centric objectives (e.g. promotions). We will add a reference to the paper (Mehrotra, Xue, Lalmas. *Bandit based optimization of multiple objectives on a music streaming platform*, KDD 2020). Although we are not aware of the scale of the parameters used for these kind of applications, benchmarks of simple heuristics on undisclosed datasets in this paper have shown fair practical performance, which we are confident could be outperformed by our method. Going back to potential applications to adaptive clinical trials, we could also mention other examples besides vaccinology in which it is common to monitor several possibly conflicting objectives. For example one can think of clinical trials combining patient-reported outcomes (e.g. quality-of-life questionnaires) and clinical outcomes (e.g. tumour remission) or clinical trials in neurocognitive diseases that use a lot of different tests assessing different neurocognitive dimensions (ex. executive functions and memory tests). \n\n* Due to space limitation, we had to state our lower bound (Theorem 3) in the appendix, but we will move it to the main text if given some extra space for our revision, and also mention the existing lower bound of [6] (not for the $k$-relaxation). We emphasize that our lower bound is only a worse case result (in the spirit of the one derived by [11] for the problem of finding a $k$-sized subset of the top $m$ arms in a standard bandit). We prove that there exists some instances in which the sample complexity has to scale with our gaps. We will leave as an open question whether we can derive a tighter lower bound which is valid for every instance. But deriving such bounds in the presence of multiple correct outputs is known to be challenging [10].    "}, {"review_id": "Rd9XjIfHQo", "reviewer": "Reviewer_rUsc", "summary": "This paper studies a less common setting that arms are multi-variate distributions. In the expiration period, the agent seeks to identify the arm which is Pareto optimal. \n\nThis problem is formulated as a fixed-confidence identification problem. The most novel setting in that, the fixed confidence identification problem s extended for multi-objective settings. \n\nThis paper proposed a novel sampling rule called Adaptive Pareto Exploration. The central idea is to identify the two contentious arms and sample both or one of them. \n\nThe paper also gives the theoretical guarantee that  the proposed method can recommend a correct set whp after most a given number of iterations. \n\n\n\n", "questions": "1. Can the proposed method identify the full (relaxed) Pareto front?\n\n", "limitations": "No. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper proposes a principled method and provides theoretical guarantees. \n", "weaknesses": "It seems trival to me to extend the single objective best arm  identification problem to the mo setting. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. \n\n* We would like to clarify from your summary that our algorithm is not meant to identify \"the arm which is Pareto optimal\" as there might be more than one Pareto optimal arm. We propose a sampling rule called Adaptive Pareto Exploration that when combined with different stopping rules, can solve different objectives: identify the entire Pareto set ($0$-PSI in our terminology), identify the entire Pareto set and possibly a few extra arms close to it ($\\varepsilon_1$-PSI), identify at most $k$ arms that are (nearly) Pareto optimal ($\\varepsilon_1$-PSI-$k$) or identify a \"representative\" subset of the Pareto set ($(\\varepsilon_1,\\varepsilon_2)$-PSI). We hope that this clarifies our contribution and answers your question.\n\n* We strongly disagree that it is trivial to extend the single objective best arm identification problem to the mo setting. While PSI (Pareto set identification) is a natural extension of the best arm identification problem in standard bandits, PSI is actually a more challenging problem. In PSI we don't know the number of optimal arms beforehand: it can go from $1$ to $K$, while in BAI the classical assumption is that there is a single optimal arm. When relaxations are further taken into account, there are multiple valid solutions (e.g. for $\\varepsilon_1$-PSI-$k$ when the size of the Pareto set is larger than $k$, any subset of size $k$ is a valid guess), which creates some additional difficulties even in the uni-dimensional setting [10]. It is true that our sampling rule shares a common structure with that of existing adaptive BAI algorithms which rely on playing two contentious arms ($b_t$ and $c_t$ in our paper), often the empirical best arm  and a contender (LUCB, UGap or more recently Top Two algorithms). However, it actually took us several iterations to come up with the right definitions for $b_t$ and $c_t$ for the PSI problem, which interestingly do not exactly coincide with the choices in prior BAI algorithms when $D=1$ (see Appendix E). You can also read our answer to reviewer 9Ln4 for a better intuition about our definition of $b_t$ and $c_t$, which will be included in our revision. As a start, in the multi-objective case we no longer have an ``empirical best arm\" but a set of arms of random size that could equally be optimal. Likewise, many results and techniques known so far for BAI do not directly apply to our setting and our analysis required specific results to pin down the behavior of our algorithm: Lemma 3 and Lemma 4. We will be happy to sketch their proof (and their crucial ingredient Lemma 8 currently stated in appendix) if we are given an extra page for our revision."}]

Author rebuttal:

Meta-review: Bandits problems with multiple objectives is a timely topic. The paper proposes a new theoretical framework to pose concrete questions in the form of several relaxations of PSI (Pareto Set Identification), the mutli-objective analog of Best-Arm-Identification (BAI). The theoretical results seems strong, novel and interesting and are complemented by an empirical study.
Decision: Accept (poster)