FraPPE: Fast and Efficient Preference-Based Pure Exploration

We thank the reviewer for taking their time to review our work. We respond to their concerns below.

1. Standard definition of partial order: We use the classical definition of order induced by a preference cone in vector optimisation literature [6,7]. This has been used across the board in the Pareto set identification with bandit feedback literature [2,3,4,5].

2. $L$-parameter exponential family: We think that there is a miscommunication here. Now, we include the following detailed definition of $L$-parameter exponential family in the paper.

• Definition: Specifically, let us consider an exponential family defined as $f(\boldsymbol{X}\vert\boldsymbol{\theta}) := h(\boldsymbol{X}) \exp\left( \langle \eta(\boldsymbol{\theta}), T(\boldsymbol{X})\rangle - \psi(\boldsymbol{\theta})\right)$ with $\boldsymbol{\theta} \in \Theta \subseteq \mathbb{R}^L$ and $\boldsymbol{X} \in \mathbb{R}^L$. Then $\eta : \Theta \rightarrow \mathbb{R}^s$ is the natural parametrization for some $s \geq L$. $T : \mathbb{R}^L \rightarrow \mathbb{R}^s$ is the sufficient statistic for the natural parameter. $h(\boldsymbol{X})$ is the base density such that $h: \mathbb{R}^L \rightarrow [0,\infty)$. Finally, $\psi(\boldsymbol{\theta}) = \log \left( \int_{\mathcal{X}} h(\boldsymbol{X}) \exp\left( \langle \eta(\boldsymbol{\theta}), T(\boldsymbol{X})\rangle \mathrm{d}\boldsymbol{x}\right) \right)$ is the log-normaliser or log-partition function. It is fully defined by $\eta$, $T$ and $h$. Specifically, the valid natural parameters are the ones for which $\psi(\eta(\boldsymbol{\theta}))$ remains finite (Chapter 18 in [8]).

3. Lemma 2: Thank you for pointing this out for elaboration.

• a. $\epsilon$ is the closeness parameter necessary to define the ''good events''. These events are crucial to ensure convergence of the sequential estimation problem. In our case, the two events are (i) Convergence of the sub-differential set, and (ii) Convergence of the objective function with respect to mean estimates for any allocation policy (Equation (18) and (19)) with respect to mean estimates.

• b. Although, as correctly pointed out by the reviewer, there is no formal definition for $\tilde{\epsilon}$, which arises as for estimating the minimum time required to ensure convergence of allocation policy $\boldsymbol{\omega_t}$ to $\boldsymbol{\omega}^{\star}(M)$ and consequently $F(\boldsymbol{\omega_t}\mid M)$ to $F(\boldsymbol{\omega}^{\star}(M)\mid M)$. Mathematically, $\|F(\boldsymbol{\omega}^{\star}(M)\mid M)-F(\boldsymbol{\omega_t}\mid M)\| \leq 5\epsilon$ holds for $T\geq \bar h(T)$ (Theorem 5). Now, if $T \geq \left(\frac{2}{\tilde{\epsilon}}\right)^{11}$, then we get $T-\bar h(T) \geq \frac{T}{1+\tilde{\epsilon}}$. This is a standard algebraic trick used in the existing literature (for e.g., [1]).

Both these constants can be arbitrarily small, and hence, the asymptotic optimality of FraPPE follows. We will incorporate the definition of $\tilde{\epsilon}$ in the updated manuscript.

We hope that our explanations clarify all the doubts regarding correctness of our results and will motivate the reviewer to adjust their score appropriately. We remain available for further clarifications and discussions.

Reference:

[1] Wang, Po-An, Ruo-Chun Tzeng, and Alexandre Proutiere. "Fast pure exploration via frank-wolfe." Advances in Neural Information Processing Systems 34 (2021): 5810-5821.

[2] Ararat, C. and Tekin, C. (2023). Vector optimization with stochastic bandit feedback. In PMLR.

[3] Karagözlü, E. M., Yıldırım, Y. C., Ararat, C., and Tekin, C. (2024). Learning the pareto set under incomplete preferences: Pure exploration in vector bandits. PMLR.

[4] Shukla, Apurv, and Debabrota Basu. (2024). Preference-based pure exploration. NeurIPS.

[5] Crepon, E., Garivier, A., and M Koolen, W. (2024). Sequential learning of the Pareto front for multi-objective bandits. PMLR.

[6] Jahn, Johannes, ed. Vector optimization. Berlin: Springer, 2009.

[7] L{"o}hne, Andreas, Vector optimization with infimum and supremum, Springer Science & Business Media, 2011.

[8] DasGupta, Anirban. "The exponential family and statistical applications." Probability for Statistics and Machine Learning: Fundamentals and Advanced Topics. New York, NY: Springer New York, 2011. 583-612.

Thank you for your detailed responses to my questions. Your answers have sufficiently addressed my concerns. I recommend incorporating this discussion into the main text or the appendix of the paper to enhance its completeness and clarity.

Additionally, please use the formal definition of the L-parameter exponential family in the next version of the paper, and clearly specify the relationship and distinction between the dimensions of $X$ and $\Theta$.

Based on these improvements, I will be updating my score to borderline accept.

Clarification on $\tilde{\epsilon}:$ We think there is a misunderstanding here. We address the question in two layers.

In lower bound-based pure exploration literature, we try to solve the lower bound with empirical estimates of means of the underlying arms at each time step. Thus, often the proof consists of two concentration phenomena: concentration of empirical mean to true mean and then concentration of the lower bound to the true one due to using estimates and alt-set optimisation. Finally, they together lead to the convergence in allocation and thus, correctness. This always introduces an $\epsilon$ to control the convergence, and often we introduce other parameters to explicitly write the time to concentrate to the aforementioned desired events. For example, $\epsilon$ and $\tilde{\epsilon}$ in our case; $\epsilon$ and $\eta$ in seminal work of [1]; $\epsilon$ and $\tilde{\epsilon}$ in [3] that developed the Frank-Wolfe method; and the following literature [2,4,5].

One universal observation is that the $1/\epsilon$ and $1/\tilde{\epsilon}$ terms that appear in these upper bounds are independent of $\delta$. Also, note that given any fixed $\delta$, we choose $\epsilon$ and $\tilde{\epsilon}$ for proving the upper bound. Thus, first we divide the upper bound by $\log(1/\delta)$ and take $\delta \rightarrow 0$. This vanishes all the $1/\epsilon$ and $1/\tilde{\epsilon}$ dependent terms. Now, we can take the limits of the upper bound w.r.t. $\epsilon$ and $\tilde{\epsilon}$ (page 29-30, [1]; page 29, [2]; Appendix I.2., [3]; page 27-28, [4] etc.).

If this limit matches with the lower bound, we call the algorithm "asymptotically optimal". We follow this nomenclature while clarifying this nuance in of setting $\epsilon$ and $\tilde{\epsilon}$ arbitrarily small in Lemma 2.

2. An elaborate proof and how we get to the "asymptotic optimality".

We provide below a detailed discussion of the proof and why taking $\tilde{\epsilon} \rightarrow 0$ is accepted in Lemma 2. We omitted this as this algebraic trick has been proposed in [3], which is a very standard work in the domain and proposes the use of Frank-Wolfe optimiser for asymptotically optimal BAI. Later on this has been re-iterated through the literature. We will add now the following elaboration for completeness.

Step 1: Let us remind of the good events:

Event $G_1(t)$: The approximation error of solution in the Frank-Wolfe updates (Equation 7) is bounded by $\epsilon$. $G_1(t) := \lbrace\max_{\boldsymbol{x}\in\Delta_K}\min_{\boldsymbol{h}\in H_{F(.|\hat M_t)(\boldsymbol{\omega_{t-1}}, r_t)}} (\boldsymbol{x} - \boldsymbol{\omega_{t-1}})^{\top} \boldsymbol{h} - \epsilon > \max_{\boldsymbol{x}\in\Delta_K}\min_{\boldsymbol{h}\in H_{F(.|M)(\boldsymbol{\omega_{t-1}}, r_t)}} (\boldsymbol{x} - \boldsymbol{\omega_{t-1}})^{\top} \boldsymbol{h} \rbrace$

Event $G_2(t)$: The error in objective function due to using the empirical means are bounded by $\epsilon$.

Hence, the Frank-Wolfe optimiser can stop when it is close to the true maximum.

Following the concentration results, we can show that $G_1(t)\cap G_2(t)$ holds true, and thus, by Theorem 5, $F(\boldsymbol{\omega}^{\star}(M)|M) -F(\boldsymbol{\omega_t}|M) < 5\epsilon$ after time $t\geq \bar{h}(T)$.

Here, $\bar{h}(T) = \min\lbrace t \in \mathbb{N} : t\geq T^{2/11}\underline{h}(T), \sqrt{\frac{t}{K}} \in \mathbb{N}\rbrace$, $\underline{h}(T) = \min\lbrace t \in \mathbb{N} : t\geq T^{8/11} + 2, \sqrt{\frac{t}{K}} \in \mathbb{N}\rbrace$, and $T\geq \max \lbrace \left(\frac{35D}{\epsilon}\right)^{11},T_{\epsilon,D}^{\frac{11}{8}}, (4K+1)^{\frac{11}{8}}\rbrace$. $D$ and $T_{\epsilon,D}$ are defined in the paper.

Step 2: Now, given $G_1(t)\cap G_2(t)$ holds true, we have $\min(\tau,T) \leq \bar{h}(T) + \sum_{t=\bar{h}(T)}^T \mathbf{1}\lbrace \tau > T\rbrace,$ where $\tau$ is the stopping time of FraPPE. Thus, $\min(\tau,T) \leq \bar{h}(T) + \sum_{t=\bar{h}(T)}^T \mathbf{1}\lbrace tF(\boldsymbol{\omega_t}\mid \hat{M}_t)< c(t,\delta)\rbrace.$

Now, for $t\geq \bar{h}(T)$, $F(\boldsymbol{\omega_t}\mid \hat{M}_t) < F(\boldsymbol{\omega_t}\mid M) - \epsilon < F(\boldsymbol{\omega}^\star(M)|M) - 6\epsilon.$

Therefore, we have, $\min({\tau,T}) \leq \bar{h}(T) + \sum_{t=\bar{h}(T)}^T \mathbf{1}\lbrace t(F(\boldsymbol{\omega^\star}(M)|M) - 6\epsilon)< c(t,\delta)\rbrace \leq \bar{h}(T)+ \frac{c(T,\delta)}{F(\boldsymbol{\omega_t}^{\star}(M)|M) - 6\epsilon}.$

Please check the next comment for continuation.

We thank the reviewer for reviewing and acknowledging our work. We respond to the concern raised below:

Covariance matrix: In the problem formulation, we did not highlight the covariance matrix of reward distribution as it is known in our setup and the main challenge in bandits is the means of the reward distributions being unknown. It is also reflected in the derivation of the lower bound in [1]. Note that, we also consider the reward distributions can have higher moments. In Assumption 1, we adhered to the definition of a multi-parameter exponential family (Chapter 18 in [2]), where $\psi(\eta(\boldsymbol{\theta}))$ is the log-partition function and $\eta$ is the natural parametrisation. If we differentiate $\psi$ w.r.t. $\eta$, we get the mean $\boldsymbol{\mu}$, and the second-order derivative $\nabla_{\eta(\boldsymbol{\theta})}^2 \psi(\eta(\boldsymbol{\theta}))$ yields the covariance matrix. We will explicitly mention the covariance in Section 2 to avoid any confusion around the definition. %\todo[inline]{Section 2 he said, change this writing.}

Figure 1: Thank you for pointing this out. Although the intend was to show that different preference cone results in different Pareto optimal arms, but they can have intersection. We will change it such that there are no intersections so that it is more clearly understandable.

Stationary policy: By stationary policy, we wanted to convey that the pure policies (stands for playing an arm) does not change over time. We will definitely include a formal definition.

Line 205: We will formally define pure policies (policies that have all the probability mass on a single arm). Thank you for pointing this out.

Choice of $r_t$: As per the existing literature on Frank-Wolfe [3], the approximation parameter $r_t$ should shrink at a rate $\Omega(1/t)$. It ensures the convergence of empirical allocation $\boldsymbol{\omega}_t$ to optimal allocation $\boldsymbol{\omega}^{\star}(M)$ (Theorem 5). In practice, we have chosen $r_t = \frac{K}{t^{0.9}}$.

Convergence of sub-differential set: First, we prove continuity of the mapping from allocation policy to sub-differential set in Corollary 1 (Appendix D.2). Then, we show the convergence of Frank-Wolfe iterates (Equation (7)) while we iteratively optimise over the allocation policy (Appendix D.3).

Comparison table: This a very nice suggestion. With the additional available page, we will definitely include a table that summarises the complexity of different approaches to solve Pareto set identification and their corresponding complexity.

Contribution and technical challenges: In this paper, we successfully address the open problem posed in [4] to propose the first computationally efficient and asymptotically optimal algorithm, that works for arbitrary preference cones and exponential family distributions, and also achieves the lowest sample complexity and probability of error for identifying the exact set of Pareto optimal arms. We mention all our contributions in line 88 to 107 in the main manuscript. The key technical challenges are discussed in the beginning of Section 3.1 and Section 3.2, i.e., solving optimisation over alternating instance and Pareto optimal policy set. Complying with the reviewer's remark, we will again summarise the technical challenges tackled in this work.

We hope that we have addressed all the concerns. We are eager to discuss further if the reviewer has more concerns or comments.

Reference:

[1] Shukla, Apurv, and Debabrota Basu. (2024). Preference-based pure exploration. NeurIPS.

[2] DasGupta, Anirban. "The exponential family and statistical applications." Probability for Statistics and Machine Learning: Fundamentals and Advanced Topics. New York, NY: Springer New York, 2011. 583-612.

[3] Wang, Po-An, Ruo-Chun Tzeng, and Alexandre Proutiere. "Fast pure exploration via frank-wolfe." Advances in Neural Information Processing Systems 34 (2021): 5810-5821.

[4] Crepon, E., Garivier, A., and M Koolen, W. (2024). Sequential learning of the Pareto front for multi-objective bandits. PMLR.

Dear Reviewer,

We are grateful for the time and attention you have devoted to evaluating our submission. Your detailed and constructive feedback is much appreciated.

Warm regards, The Authors

We thank the reviewer for their valuable review and remarks. We respond to the concerns raised below:

1. Experimental validation and computational bottleneck:

• a. Runtime of FraPPE: While only using CPUs (without parallel processing and tensorization), each iteration of FraPPE takes $\sim 64$ milliseconds/iteration for COVBOOST ($19$ arms and $3$ objectives). While for DB [1] ($128$ arms and $2$ objectives), FraPPE clocked in $\sim 98$ milliseconds/iteration. For synthetic data with correlated objectives ($5$ arms and $2$ objectives), it takes $\sim 14.6$ milliseconds/iteration. These results are obtained by averaging over 1000 iterations.

• b. Runtime of baselines: The implementations available in the literature differ in their setup and programming languages: [2] uses Julia, [3] uses C++. In contrast, to make the code accessible to wider audience, we chose Python3 for implementation with only three well-known packages: Numpy, CVXPY, and Scipy. Thus, we surmise it would be unfair to compare the clock runtimes of the different baselines implementations. But resonating with the reviewer's remark, we have now conducted a runtime analysis with varying $K$, $L$ to validate our theoretical claims.

• c. Conic programming: Yes, we agree that conic programming is the computationally costliest module here. Though we believe while solving the lower bound, conic programs are unavoidable as it is required to find the Pareto for generic cones. Thus, it has been a part of the open problem posed by [2], i.e. to reduce the computational complexity per iteration up to the complexity of Pareto set computation.

• d. Larger dataset- DB [1]: We have tested on all the datasets used in the SOTA paper for exact Pareto set identification: PSIPS [3]. We are currently testing FraPPE on the DB (Disc Brake) dataset ($128$ arms and $2$ objectives) that presents an efficiency and safety optimization problem in disc brake manufacturing for automotives. In the literature, larger datasets like DB are used only to attain $\epsilon$-approximate Pareto set identification [5,6], while FraPPE aims for exact identification and succeeds as per the preliminary results.

Comparison table: This is indeed a very nice suggestion. With the extra available space, we will definitely include a table that summarises the complexity of different approaches to solve Pareto set identification and their corresponding complexity.

FraPPE in Combinatorial Bandits: We think like most of the algorithmic framework that exists for solving pure exploration in multi-objective bandits, for e.g., successive arm-elimination [1] or Bayesian posterior sampling based [2] etc., FraPPE can also be extended to solve pure exploration in combinatorial bandits. That means the goal will be to identify the optimal combinatorial or subset of arms among $2^K$ possible subsets (Or a policy with basis consisting pure policies corresponding optimal subset of arms) that maximises the reward . Additionally, the agent will observe feedback for each of the arms in the subset chosen to play at any time step. Although we think this problem is more complex due to exploration among exponentially large $2^K$ options rather than usual $K$ actions. This bottleneck calls for careful adaptation of the existing lower bound to the combinatorial setup (that might depend on complexity of differentiating between the optimal subset and the second best subset of arms). Still, this problem seems solvable by adapting FraPPE directly with necessary extensions.

Mild deviations in theoretical assumptions: The only two assumptions that we require are: the knowledge of the cone $\mathcal{C}$ and the reward distribution being in an exponential family with non-zero second moment. The first one is a fundamental requirement as the lower bound of [6], which is our starting point, requires this. If we have a misspecified cone, the algorithm would still run and identify a part of the Pareto optimal arms but we cannot theoretically say anything about correctness and optimality. The second one is more of a theoretical requirement to prove optimality of FraPPE. The lower bound and the algorithmic technique would work for any distribution. But since the GLRT stopping rule is known to be tight for exponential families, not only FraPPE but any lower bound-driven pure exploration algorithm [7,8,9] even in simple best arm identification assumes an exponential family to prove optimality [1,2,6]. In brief, we can run FraPPE for instances deviating from these assumptions but we cannot guarantee the theoretical goodness any more.

We hope that we have addressed all the concerns. We are eager to discuss further if the reviewer has more concerns or comments.

References:

[1] Crepon, E., Garivier, A., and M Koolen, W. (2024). Sequential learning of the Pareto front for multi-objective bandits. AISTATS.

[2] Kone, C., Jourdan, M., and Kaufmann, E. (2025). Pareto set identification with posterior sampling. AISTATS.

[3] Tanabe, R. and Ishibuchi, H. (2020). An easy-to-use real-world multi-objective optimization problem suite. Applied Soft Computing, 89:106078.

[4] Ararat, C. and Tekin, C. (2023). Vector optimization with stochastic bandit feedback. In PMLR.

[5] Karagözlü, E. M., Yıldırım, Y. C., Ararat, C., and Tekin, C. (2024). Learning the pareto set under incomplete preferences: Pure exploration in vector bandits. PMLR.

[6] Shukla, Apurv, and Debabrota Basu. (2024). Preference-based pure exploration. NeurIPS.

[7] Garivier, A. and Kaufmann, E. (2016). Optimal best arm identification with fixed confidence. COLT.

[8] Wang, P.-A., Tzeng, R.-C., and Proutiere, A. (2021). Fast pure exploration via Frank-Wolfe. NeurIPS.

[9] Degenne, R., Ménard, P., Shang, X., and Valko, M. (2020). Gamification of pure exploration for linear bandits. ICML.

We thank the reviewer for acknowledging our work and taking their time to review. We respond to the questions raised below:

1. Section 3.3 : In this section, we leverage the structure of the alternating instance $\tilde{M}^{L \times K}$ to gain computational efficiency for the two innermost minimisation problems in Equation (3).

• (a) Direct optimisation over $\tilde{M}^{L \times K}$ can have complexity $\mathcal{O}(KL)$, since optimising an $L$-dimensional vector inside a cone has complexity $\mathcal{O}(L)$. With the polar cone representation of the alternating instances (Proposition 1), $\tilde{M}$ can be expressed with $\boldsymbol{y}, \boldsymbol{\pi}_i^{\star}, \boldsymbol{\pi}_j$. Here, $\boldsymbol{y}$ is an $L$-dimensional vector on the boundary of the polar cone of the given preference cone $\mathcal{C}$. Thus, for a fixed $\boldsymbol{\pi}_i^{\star}$ and $\boldsymbol{\pi}_j$, we now optimise over an $L$-dimensional vector rather than a $L\times K$ matrix.

• (b) Further with this reduction, we observe that $\boldsymbol{z}^L$ and $\boldsymbol{y}^L$ are defined on the cone $\mathcal{C}$ and its polar cone $\mathcal{C}^{\circ}$. Thus, any efficient second order conic program solver (for e.g., CVXPY) can solve both the optimisation problems in $\mathcal{O}(L)$ rather than $\mathcal{O}(L^2)$.

Hence, the total computational gain achieved in Section 3.3 is $\mathcal{O}(KL^2) \rightarrow \mathcal{O}(L)$.

2. L-parameter exponential family: Since we adopted the standard definition of multi-parameter exponential family from statistics ((Chapter 18 in [1])), which is also a generalisation of multivariate Gaussian of dimension $L$ with mean $\boldsymbol{\mu}$ and covariance $\boldsymbol{\Sigma}$, we omitted a detailed discussion. Thanks for the remark. We clarify it here and must add the details with the extra page available.

• Definition: Specifically, let us consider an exponential family defined as $f(\boldsymbol{X}\vert\boldsymbol{\theta}) := h(\boldsymbol{X}) \exp\left( \langle \eta(\boldsymbol{\theta}), T(\boldsymbol{X})\rangle - \psi(\boldsymbol{\theta})\right)$ with $\boldsymbol{\theta} \in \Theta \subseteq \mathbb{R}^L$ and $\boldsymbol{X} \in \mathbb{R}^L$. Then $\eta : \Theta \rightarrow \mathbb{R}^s$ is the natural parametrization for some $s \geq L$. $T : \mathbb{R}^L \rightarrow \mathbb{R}^s$ is the sufficient statistic for the natural parameter. $h(\boldsymbol{X})$ is the base density such that $h: \mathbb{R}^L \rightarrow [0,\infty)$. Finally, $\psi(\theta) = \log \left( \int_{\mathcal{X}} h(\boldsymbol{X}) \exp\left( \langle \eta(\theta), T(\boldsymbol{X})\rangle \mathrm{d}\boldsymbol{x}\right) \right)$ is the log-normaliser or log-partition function. It is fully defined by $\eta$, $T$ and $h$. Specifically, the valid natural parameters are the ones for which $\psi(\eta(\theta))$ remains finite.

We hope that our response have addressed the concerns and questions. We remain available for further discussion.

Reference: [1] DasGupta, Anirban. "The exponential family and statistical applications." Probability for Statistics and Machine Learning: Fundamentals and Advanced Topics. New York, NY: Springer New York, 2011. 583-612.

Dear reviewer,

As the rebuttal period is coming to the end, we thank you for taking time to thoroughly review our work. We appreciate your constructive feedback.

Regards, Authors

We thank the reviewer for taking time to review our work, and for appreciating the novelty and clarity of our contributions. We respond to the questions below, while we include the promising improvements in our updated draft.

1. Experimental validation and computational bottleneck:

• a. Runtime of FraPPE: While only using CPUs (without parallel processing and tensorization), each iteration of FraPPE takes $\sim 64$ milliseconds/iteration for COVBOOST ($19$ arms and $3$ objectives). While for DB [1] ($128$ arms and $2$ objectives), FraPPE clocked in $\sim 98$ milliseconds/iteration. For synthetic data with correlated objectives ($5$ arms and $2$ objectives), it takes $\sim 14.6$ milliseconds/iteration. These results are obtained by averaging over 1000 iterations.

• b. Runtime of baselines: The implementations available in the literature differ in their setup and programming languages: [2] uses Julia, [3] uses C++. In contrast, to make the code accessible to wider audience, we chose Python3 for implementation with only three well-known packages: Numpy, CVXPY, and Scipy. Thus, we surmise it would be unfair to compare the clock runtimes of the different baselines implementations. But resonating with the reviewer's remark, we have now conducted a runtime analysis with varying $K$, $L$ to validate our theoretical claims.

• c. Conic programming: Yes, we agree that conic programming is the computationally costliest module here. Though we believe while solving the lower bound, conic programs are unavoidable as it is required to find the Pareto for generic cones. Thus, it has been a part of the open problem posed by [2], i.e. to reduce the computational complexity per iteration up to the complexity of Pareto set computation.

• d. Larger dataset- DB [1]: We have tested on all the datasets used in the SOTA paper for exact Pareto set identification: PSIPS [3]. We are currently testing FraPPE on the DB (Disc Brake) dataset ($128$ arms and $2$ objectives) that presents an efficiency and safety optimization problem in disc brake manufacturing for automotives. In the literature, larger datasets like DB are used only to attain $\epsilon$-approximate Pareto set identification [5,6], while FraPPE aims for exact identification and succeeds as per the preliminary results.

2. Specification of the cone:

• a. Practicality of knowing $\mathcal{C}$: We assume to know the preference cone following the present literature of PrePEx, where the SOTA results are mostly available for the positive orthant as the cone. Knowledge of $\mathcal{C}$ is available in multiple real-world systems: polyhedral cones are used in aircraft design optimisation [7], positive orthant cone ($\mathbb{R}^L_{+}$) are used in Portfolio optimization balancing return, risk, and liquidity [8], customised asymmetric cones are used in climate policy optimization with multiple national goals [9].

• b. Learning $\mathcal{C}$: We agree that sequentially learning the cone from multiple expert's feedback while exploring is an interesting problem with its own set of challenges. But if we do not know $\mathcal{C}$ or encounter misspecification, the lower bound of [10] is not valid and we should derive a new lower bound. It is an ongoing study and we will mention it in future works.

We hope that our response have addressed the concerns and questions. We remain available for further discussion.

References:

[1] Tanabe, R. and Ishibuchi, H. (2020). An easy-to- use real-world multi-objective optimization problem suite. Applied Soft Computing, 89:106078.

[2] Crepon, E., Garivier, A., and M Koolen, W. (2024). Sequential learning of the Pareto front for multi-objective bandits. PMLR.

[3] Kone, C., Jourdan, M., and Kaufmann, E. (2024). Pareto set identification with posterior sampling.

[4] Ararat, C. and Tekin, C. (2023). Vector optimization with stochastic bandit feedback. In PMLR.

[5] Karagözlü, E. M., Yıldırım, Y. C., Ararat, C., and Tekin, C. (2024). Learning the pareto set under incomplete preferences: Pure exploration in vector bandits. In PMLR.

[6] Bradley, R. A. and Terry, M. E. (1952). Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika.

[7] Mavrotas, G. (2009). Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems. Applied Mathematics and Computation.

[8] Ehrgott, M. (2005). Multicriteria Optimization. Springer.

[9] Keeney, R. L., & Raiffa, H. (1993). Decisions with Multiple Objectives: Preferences and Value Trade-Offs. Cambridge University Press.

[10] Shukla, Apurv, and Debabrota Basu. "Preference-based pure exploration." Advances in Neural Information Processing Systems 37 (2024): 17313-17347.

Dear reviewer,

Thanks for the time spent reviewing our work. We appreciate your constructive feedback.

Regards, Authors