Preference-based Pure Exploration

We thank the reviewer for the time spent reviewing and pointing out several notational issues to improve the manuscript. We have done a proofreading of the paper and fixed the typos and issues. We address the other concerns here.

1. Novelty with respect to Track and Stop: As pointed out by reviwer E3uE: ``While the overall structure closely follows the track-and-stop literature, there seems to be a lot of technical novelty in its extension to the pareto front setting. The characteristic time has a much more complicated geometric structure, which is reflected in the lower bound. New concentration inequalities need to be derived for the pareto frontier estimation (along with a novel distance)." We would like to build upon observation and highlight the salient features of our contribution and the relation to existing work.

2. Purpose of convexification: Convexification serves several purposes not limited to providing computational benefits. Without optimising over the convex set, we cannot guarantee that the algorithm is asymptotically optimal. In particular Theorem 4, claim (4) will not hold. Therefore, tracking the lower bound as per Track-and-Stop strategy will not lead to asymptotic optimality. There are other key points which will not hold if we do not optimize over the convex hull. For example, we cannot directly use Donsker-Vardhan in the proof of Lemma 6 but we have to prove compactness and other properties of the original non-convex set.

3. Convexification of Characteristics Time: In the setting with Gaussian bandits, as we show Theorem 2 in the paper, nothing is lost since we are able to get exact form of the hardest instance analytically. In the non-Gaussian setting, we need to conduct a separate study, both computational and theoretical, in order to study the gap between solutions of the original optimization problem and the convex relaxation. It will non-trivially depend on the interaction of the preference cone and the space of confusing instances. This would be a interesting avenue for future work. Further, please see lines 316-324 in the updated paper.

4. Explaining the maximisation problem in Equation (1): For better understanding, we explain the maximisation problem of Equation (1) as "Alternatively, this vector optimization problem can be represented in the policy space as finding a policy $\pi \in \Delta_K$ supported on the Pareto optimal set of arms. This is given by..." (line 189-191 in revised manuscript). Let us know if that clarifies your concerns.

We hope that our rebuttal addresses your concerns and questions. We are eager to discuss if you have further queries.

(1) Novelty with respect to TaS: We believe that there is a confusion regarding novelty with respect to TaS, and we would really like to clarify it.

Track-and-Stop provides a generic wrapper for designing lower bound-based pure exploration algorithm. But for the preference-based pure exploration problem the lower but bound is significantly different than that of BAI. Thus, we have to derive a new lower bound (and a ``good" relaxation) and propose multiple components to design PTnS, which were absent in the TaS paper and the following literature.

We enlist these components here:

1.1) Stopping rule: The standard Chernoff-based stopping rule (Eq.(6) of Kauffmann et. al., JMLR, 2016) do not work for the PrePEx problem as here the term inside KL needs to consider preference (Equation (8), line 338). Thus, we proposed a new preference-aware stopping rule. This requires deriving a a novel concentration inequality (Theorem 5). These design contributions and their theoretical validity (which is one of the main contributions of the paper) are highlighted from line: 331-351. This is a contribution to both the design as well as analysis over and above the existing TaS algorithms.

1.2) Use of convexified set for tracking: Creating the convex-hull of alternating instances, and further using that for tracking and computing allocations is novel. It has luckily not been needed in existing BAI techniques. We dedicated Section 4.1. for this and now also add a commentary on the need and impact of convexification following your previous feedback.

1.3) Analysis of PreTS: The analysis of PreTS (Section 5) involves several new theoretical techniques and results: (a) defining the distance metric between pareto fronts instead of Hausdroff metric (Definition 8), (b) showing concentration of good event with respect to this metric (Lemma 4), and (c) a preference-dependent concentration of difference of means (Lemma 2). We extend the discussion in line 91-94 to highlight these components.

We hope that this exposition of the non-trivial changes in algorithm design and analysis would be able to clarify your concern regarding novelty of PreTS with respect to TaS. Based on the previous feedback, we have further added an explicit remark in the main paper highlighting these novelties with respect to TaS.

2. A case for convexification: The advantages of convexification are of both statistical and computational in nature. A thorough discussion of the computational benefits/tradeoffs with existing approaches was avoided since this was not the main objective of the paper, and more numerical and optimization-based in nature. Since this paper is mostly theoretical and statistical in nature, and we had to explain several novel design and analysis ideas, we feel that computational discussions are best for a seperate work. Now, we have added a discussion at the end of Section 4.1. to clarify the need and impact of convexification. We quote it here verbatim:

``Discussion: Cost and Need of Convexification. For Gaussian bandits, as we can get the analytical form of the most confusing instance $\tilde{M}$ (Theorem 2), we do not pay any extra cost of convexification. In the non-Gaussian settings, where we cannot find such analytical forms for the most confusing instances, the minimum value of the inner minimisation problem under convex hull (Equation (5)) can go lower than the minimum value found in the original non-convex set of instances (Equation (3)). Thus, the characteristic time attained by solving the convex relaxation might be either higher than or equal to that of the original lower bound (Equation (3)). Hence, an algorithm solving the convex relaxation might have higher stopping time. But convexification is essential for computational feasibility of a lower bound-tracking algorithm for PrePEx, and also to prove Theorem 4, which is essential to statistically design a tracking-type algorithm. In future, it will be interesting to study this computational-statistical trade-off.’’

3. Thanks, we agree with this observation. We remove the qualifier "asymptotically optimal" for PreTS from the paper. We edit line 13 as "matching sample complexity upper bound” (line 13) - ``a convex relaxation of the lower bound as the sample complexity upper bound". We also edit the other three mentions (line 93, 381, 391) similarly, and mention that PreTS tracks a convex relaxation of the lower bound and achieves the corresponding sample complexity for general reward functions.

Let us know if this response clarifies our concerns. We would be happy to elaborate further if it does not. If we have successful to clarify, we would ask you to kindly reconsider your score. Thanks again for reviewing our work.

We would like to thank the reviewer for appreciating the strength of our contributions. We have rectified the errors, typos, and notational issues in our revised manuscript.

We thank the reviewer for acknowledging the strengths and novelty of the contributions along with pertinent questions regarding the computational approach. We respond to them here.

1. Cost of Convex Relaxation: In the setting with Gaussian bandits, as we show Theorem~2 in the paper, nothing is lost since we are able to get exact form of the hardest instance analytically. In the non-Gaussian setting, where we cannot find such analytical form for the confusing instance, we observe that the min value of the inner minimisation problem under convex hull can be lower than the minimum value found in the original non-convex set of instances. Thus, the characteristic time attained by the algorithm using the convex relaxation can be higher than that of the original lower bound. Thus, an algorithm solving the convex relaxation might have higher stopping time. Further, please see lines 316-324 in the updated paper.

2. What happens in problem instances where the optimal action is not in the relaxed region? Since our approach takes the convex hull of the feasible set, which is a super-set of the true set of alternating instances, the optimal action set always lies in this set.

3. Technical Novelties and Insights: The technical novelties of this work can be categorised into three parts: (i) lower bound: taking the policy space perspective, (ii) algorithm design: convexification of the lower bound and a new stopping rule and (iii) proving asymptotic optimality of PreTS requires coming up with a new distance metric and establishing concentration inequalities under these metrics.

We hope that our response addresses your questions. We would be glad to respond if you have any further query.

We would like to thank the reviewer for pointing out several avenues for improving our work. We address the concerns below.

Editorial edits: We have revised our manuscript to rectify all the errors and typos as mentioned by the reviewer.

Identification of the Pareto Front: This paper is about identifying the entire Pareto front. This resonates the line of literature paved by Sequential Learning of the Pareto Front for Multi-objective Bandits", crepon, Garivier, Koolen AISTATS 2024, and Pareto Front Identification from Stochastic Bandit Feedback" Auer et. al. AISTATS 2016. They consider similar problems but without generic preferences and linear bandit feedback. Similar but not identical problem was considered in "Adaptive algorithms for relaxed pareto set identification", Kone et. al. NeurIPS 2023, wherein an approximation of the Pareto Set has to be identified. Our problem is a non-trivial generalization of those papers in the sense that, we consider generic preferences (described through a preference cone) and linear bandit feedback.

Terminology: Thank you for pointing out. The word "support" suffices for our purposes.

Asymptotic Optimality and Theorem 6: $\mathcal{T}_{F}$ is the characteristic time associated with PrePEx problem. You are indeed correct, the claim of Theorem 6 is that the proposed algorithm is asymptotically optimal.

We hope that our response addresses the reviewer's questions. Let us know if you have any other query.