Constrained Pareto Set Identification with Bandit Feedback

We appreciate the reviewer's thoughtful feedback and detailed evaluation of our work. Below, we address each point raised by the reviewer.

• Weaknesses

  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.
  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 $δ$).
  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.

• Questions

  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.

  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.

  3. For $𝛿=0.1$, we report below the empirical success rate of each algorithm ||e-cAPE|Uniform(U)|MD-APT+APE(A-A,Two Stage)|Racing algorithm(R-CP)| |---|---|---|---|---| |covboost|100%|100%|100%|96%| |secukinumab|100%|100%|100%|100%|

All 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.

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 $C_M^*(\mu)/4⩽ T^*_M(\mu)⩽256C_M^*(\mu),$ which shows that $C_M^*(\mu)$ is a reasonable complexity proxy for problems in $\tilde{D}$ (up to some improvable constants).

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 :

• $O(n_t d+md)$ to update the feasible Pareto set ($n_t$: size of the feasible set).
• $O(K)$ to update $M(i,j)^\pm$
• $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))$.

Per 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.

We appreciate the reviewer's thoughtful feedback and detailed evaluation of our work. Below, we specifically address each point raised in the review.

1. $α$ 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.

2. 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. The 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

• Bounding the stopping time under consecutive good events Let $τ$ be the (random) stopping time of e-cAPE, and observe that for any $T>0$, $\min(τ,T)⩽T/2+\sum_{t=T/2}^T\mathbb{1}_{(τ>t)}.$

In 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

$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

$\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))}.$

Introducing for any subset $U\subset[K]$,

$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))},$

it follows from the definition of $W_t(S,I)$ (equation 37-39, l.980-83) that $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
$R(O^*,T)⩽\sum_{a\in O^*}σ^2\max(\frac{8g(T,𝛿)}{\eta_a^2},\frac{32f(T,𝛿)}{Δ_a^2(S)}).$

• Former sub-optimal step and novel formulation of Thm 4.3

At 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)). Recalling $f(T,𝛿)=\log(\frac{2k_1KdT^α}{𝛿})\text{ and }g(T,𝛿)=4\log(\frac{2k_1K5^dT^α}{𝛿}),$ this is where we used the condition: as for $𝛿⩽ d^2/5^d$ we have $\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 $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^*)$ where $Q(\mu,U)=\sum_{a\in U}32σ^2\frac{\log(5^d/d)}{\eta_a^2}$. Applying the modification above and following the remaining proof of Thm 4.3, we prove that for any $𝛿\in(0,1)$, $\mathbb{E}[τ]⩽256σ^2 C^*(\mu)\log(128σ^2C^*(\mu)(2k_1Kd/𝛿)^{1/α})+4Q(\mu,F^c \cup O^*)+Λ_α$ where $F$ is the feasible set.

• Additional Clarification on $Λ_α$

By definition, we have (l.1330) $Λ_α=\sum_{T⩾ 1}\mathbb{P}((E^T)^c)$. We showed above that when $E^T$ holds,
$\min(τ,T)⩽ T/2+R([K],T)$ then, letting $\tilde T$ such that $\forall T⩾\tilde T,R([K],T)<T/2$,
for $T⩾\tilde T$, $τ >T⟹ (E^T)^c$. Thus, $\mathbb{E}[τ]⩽\tilde T+\sum_{T⩾\tilde T}\mathbb{P}((E^T)^c)⩽\tilde T+Λ_α,$ and $Λ_α$ is bounded using Lem D.3 in appendix.

3. 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.

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.

• Optimal algorithm for cPSI

We 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.

• Uniform exploration

We 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.
In 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. Moreover, 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).