Relation Augmented Preferential Bayesian Optimization via Preference Propagation

We greatly appreciate your thorough review and valuable comments. We have carefully addressed each of your concerns as detailed below.

Q1: The font in Fig.1 is too small. Please kindly enlarge the font in Fig.1 to make it more readable.

Thank you for your helpful comment.

We revise the layout and redrawing of all figures to improve their readability, including increasing the font size and ensuring that the overall design of the figures enhances clarity. Additionally, we will make the figure descriptions more concise and clear to further improve their accessibility. We appreciate your suggestion and will make sure that the figures are more readable and effectively communicated in the revised version.

Q2: The authors should provide a notation in the methodology section.

Thank you for your constructive feedback.

The inclusion of a notation in the methodology section will certainly make our proposed approach easier to understand. Our main notation is as shown in the table below, with all other symbols derived from those in the table.

Table1: Notation in the methodology section.

Do you have any other suggestions or feedback? Please let us know, and we will actively consider them.

We appreciate your valuable and thoughtful feedback, as well as the time you dedicated to reviewing our paper. Below, we address the questions and concerns.

Q1: Figure 4 (top plot) indicates that the original method have better Preference Num. than Augmented.

We apologize for the confusion caused by the unclear presentation in Figure 4, and we appreciate you pointing out the issue. In Figure 4 (top plot), the "number of original preferences" refers to the number of preferences that have not undergone preference propagation in each iteration, while the "number of augmented preferences" represents the new preferences added after the preference propagation process. Therefore, in RAPBO, what is actually used in each iteration is the combination of original preferences and augmented preferences. The purpose of Figure 4 is more to explore the underlying behavior of the preference propagation technique and to verify its rationality and effectiveness. We will provide a more detailed explanation of Figure 4 in the revised version to avoid any further confusion.

Q2: Why augmented relation can not be learnt in original algorithms, which indicates that relation propagation is necessary?

In previous preference based optimization works, such as PBO[1], qEUBO[2], and others, the existing pairwise preferences are directly used as datasets to train surrogate models (usually Gaussian Processes, GP). These methods do not attempt to delve deeper into the preference dataset, such as capturing additional potential preferential relations. This is why we say "existing dueling optimization methods do not make full use of the pairwise preferences collected".

In our work, RAPBO attempts to uncover the potential preferential relations between solutions within different preferences through the preference propagation technique, which allows us to perform relation augmentation and make fuller use of the existing preferences throughout the preference optimization process.

As for Figure 4, as mentioned in our response to Q1, it further explores the behavior of the preference propagation technique. Of course, since the "number of original preferences" refers to the number of preferences before preference propagation, we can, to some extent, regard this as the degree to which traditional methods utilize preferences. In contrast, RAPBO uses both the original preferences and augmented preferences during the optimization process, meaning that the "number of original preferences" plus the "number of augmented preferences" can be seen as the degree to which RAPBO utilizes the preferences. Therefore, Figure 4 could verify that RAPBO makes more fuller use of the dataset compared to traditional dueling optimization methods and indicates that preference propagation is necessary. This point has already been mentioned in the revised version of the paper (lines 430~431).

Thank you for your comprehensive review and insightful feedback. We have carefully considered your feedback and provided detailed responses below.

Q1: Lack of evidence to show the improvements of the proposed algorithm than previous algorithms.

In the paper, we design a series of experiments to verify that RAPBO achieves superior performance compared to previous algorithms. First, we showcase the effectiveness and superiority of RAPBO through experiments on a range of synthetic functions and real-world datasets (see Figures 2 and 3). As shown in the results, RAPBO shows significant improvements over the previous methods in all cases. For a more detailed results, please see the Table 1 and Table 2.

Table 1: The detailed results of dueling optimization methods on synthetic functions. In each column, an entry with the best mean value is marked in bold and underline for the runner-up. If the mean value of the best method significantly differs from the runner-up, passing a t-test with a significance level of $0.05$, then we denote it with "*" at the corresponding position.

Table2: The detailed results of dueling optimization methods on real-world datasets. In each column, an entry with the best mean value is marked in bold and underline for the runner-up. If the mean value of the best method significantly differs from the runner-up, passing a t-test with a significance level of $0.05$, then we denote it with "*" at the corresponding position.

Thank you for your valuable time and comments.

We thank you for the useful and insightful feedback and for taking the time to review our paper. We address questions and concerns below.

Q1: The GPs with kernels and priors have already defined the relation among solutions in the latent space.

Thank you for your insightful feedback, which has prompted us to think more deeply about the relationship and distinctions between our preference propagation technique and GPs with kernels.

Unlike GP with kernels, RAPBO tries to capture the potential relations between different pairwise preferences, which uses a preference propagation technique to propagate preferences over an existing dataset, thereby augmenting the relations.

Therefore, the role of our preference propagation technique is to perform relation augmentation on the dataset through preference propagation. In other words, the preference propagation technique provides a more comprehensive dataset for the surrogate model (GPs with kernels), which does not weaken the principle of Bayesian optimization.

Q2: The contributions are not strong enough. & No theoretical analysis nor design principles are used to underpin the rationality of the proposed algorithm.

Thank you for your thoughtful feedback.

Although dueling optimization relies solely on pairwise preferences without using function values, an obvious optimization performance gap exists between preference based and function value based methods. Therefore, we propose RAPBO, which aims to fill the optimization performance gap between preference based and function value based methods. To achieve this, we start from the perspective of how to make fuller use of pairwise preferences and introduce the preference propagation technique to uncover the potential preferential relations between solutions within different preferences in the dueling optimization process.

Meanwhile, we have conducted extensive experiments to verify the effectiveness and rationality of the proposed algorithm.

1. Effectiveness and superiority of RAPBO. We conduct experiments on a series of synthetic functions (see Figure 2), which collectively cover various types of optimization problems. In addition, to further highlight the effectiveness and rationality of RAPBO, we also test it on real-world tasks such as motion control and spacecraft trajectory optimization (see Figure 3).

2. Utilization of RAPBO. What's more, we delve deeper into the preference propagation technique (see Figure 4). The experimental results show that the preference propagation technique not only gathers additional preferences from existing datasets but also ensures that the newly added preferences maintain a high level of accuracy, further confirming the rationality of RAPBO.

3. Compare with function value based methods. In line with our motivation, we compare preference based methods with function value based methods (see Figure 5). The experimental results verify that, under the same cost budget, RAPBO is competitive with, or even surpasses, function value based Bayesian optimization methods in terms of optimization performance.

As for the theoretical analysis, we have made every effort to conduct it. Dueling optimization is closely related to the field of dueling bandits, and we initially sought to leverage the theoretical framework of dueling bandits to derive theoretical results. However, in the context of dueling optimization, the objective function often fails to meet common assumptions such as linearity or convexity, which forces us to explore theoretical analysis from alternative perspectives. Additionally, the proposed preference propagation technique, which incorporates GMM clustering and propagates preferences through a hypergraph structure, introduces additional complexities that further challenge theoretical analysis. Despite extensive efforts, we have not yet arrived at meaningful theoretical insights. Nevertheless, we remain committed to pursuing theoretical advancements in future work.

Table 1: The detailed results of dueling optimization methods on synthetic functions. In each column, an entry with the best mean value is marked in bold and underline for the runner-up. If the mean value of the best method significantly differs from the runner-up, passing a t-test with a significance level of $0.05$, then we denote it with "*" at the corresponding position.

Table2: The detailed results of dueling optimization methods on real-world datasets. In each column, an entry with the best mean value is marked in bold and underline for the runner-up. If the mean value of the best method significantly differs from the runner-up, passing a t-test with a significance level of $0.05$, then we denote it with "*" at the corresponding position.

We hope these responses can resolve your issues and dispel your doubts. Thank you.

Thank you for your valuable questions. We fully understand your concerns and we will address your doubts regarding the experiments.

Q1: Are the real-world datasets commonly accepted?

Thank you for your insightful question.

Regarding the experimental section, we believe that our choice of synthetic functions and real-world datasets is reasonable and commonly accepted.

First, our real-world datasets are commonly accepted. Specifically, the noisy motion control task RobotPush, widely used in Bayesian optimization like EBO [1] and TurBO [2], is a well-established real-world dataset. Additionally, the remaining two datasets, which involve spacecraft trajectory optimization problems, are also widely applied in the optimization domain. Meanwhile, as stated in our paper (lines 394–399), these datasets are all suitable for dueling optimization.

Then, as mentioned in our previous response, prior works such as KSS [3] and PBO [4] on dueling optimization primarily conduct experiments on synthetic functions. Accordingly, we initially use synthetic functions from these studies and also conduct experiments on additional synthetic functions from different types of optimization problems.

Therefore, these real-world datasets are both commonly accepted and highly suitable for solving using dueling optimization, while also aligning with our motivation.

Q2: Are the experiments of large enough scales, in both number of trials and scales of the datasets?

Thank you for your thoughtful question.

In Bayesian optimization, we assume that observing the objective function is both time-consuming and expensive, and we can only perform optimization within a limited budget [5] [6]. Consequently, in our experiments, we also set a finite budget for evaluation, consistent with previous dueling Bayesian optimization works such as HB [7] and qEUBO [8].

Moreover, whether it is our method or the compared methods, their performance curves typically rise rapidly during the early stages of optimization and gradually converge later, showing no further improvement. This pattern indicates that the budget of 100 we allocated is both sufficient and reasonable.

Q3: Are these experiment results confident enough?

Thank you for your thoughtful question.

In our experiments, RAPBO and other preference based methods exhibit relatively high standard deviations. This is because the scales of the data vary across different tasks. However, RAPBO consistently provides the best performance across all experiments, and in most cases, the standard deviation of RAPBO is the smallest compared to other methods such as PBO and KSS.

To verify that RAPBO truly outperforms other baselines in most cases, we have performed t-tests with a significance level of $0.05$. As shown in Tables 1 and 2, we denote the best method with '*' at the corresponding position if its mean value significantly differs from that of the runner-up. The results show that RAPBO statistically outperforms other baselines in the most of cases.

Q2: There is no thumb rule to determine the budget correlation between pairwise comparison and value observation.

Thank you for your feedback.

Regarding how to determine the budget correlation between pairwise comparison and value observation, it is clear that evaluating the function value is more expensive than comparing a pair of solutions. Therefore, we follow the experimental setup of PE-DPO [4], where the cost of evaluating the function value is set to be twice that of comparing a pair of solutions. To further verify that the performance of RAPBO under a fixed budget can match that of value based methods, we conduct an additional experiment where the cost of evaluating the function value is set to be 1.5 times that of comparing a pair of solutions.

Since the ratios we set are relatively small, and in real-world scenarios, evaluating the function value is often much more costly than comparing a pair of solutions, our conclusion — "under the same cost budget, RAPBO is competitive with or even surpasses function value-based Bayesian optimization methods with respect to optimization performance" — is reasonable and meaningful to practitioners.

[1] González, Javier, et al. "Preferential bayesian optimization." International Conference on Machine Learning. PMLR, 2017.

[2] Sui, Yanan, et al. "Multi-dueling bandits with dependent arms." arXiv preprint arXiv:1705.00253 (2017).

[3] Benavoli, Alessio, Dario Azzimonti, and Dario Piga. "Preferential bayesian optimisation with skew gaussian processes." Proceedings of the Genetic and Evolutionary Computation Conference Companion. 2021.

[4] "High-dimensional dueling optimization with preference embedding." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 9. 2023.

Thank you for your valuable feedback. We understand your concerns and would like to clarify them.

Q1: The number of benchmarks are limited, and the trajectories are close especially in the early 50 evaluations.

Thank you for your thoughtful feedback.

Regarding the experiments, we use more synthetic functions and real-world datasets compared to previous works such PBO [1], KSS [2] and skewGP-PBO [3] and we believe that the experiments on synthetic functions and real-world datasets are sufficient to verify the performance of our algorithm.

For the synthetic functions, we select a reasonable and sufficient set of synthetic functions to evaluate the performance of our algorithm. First, we conduct experiments on synthetic functions such as Levy and Rosenbrock, which are widely used in prior work like PBO [1] and skewGP-PBO [3]. Additionally, the synthetic functions cover a diverse range of characteristics, including multimodal landscapes (Dixon, Schwefel), complex terrains (Levy), periodic variations (Griewank), and convex optimization (Sphere, Rosenbrock). Therefore, these synthetic functions are sufficient and representative, allowing us to verify the algorithm's performance across various scenarios.

Although previous works such as [1] and [3] primarily focus on synthetic functions, we also conduct comprehensive real-world scenarios to show the performance of RAPBO, such as RobotPush, Cassini1-MINLP, and Sagas. These real-world tasks are both suitable for dueling optimization and aligned with our research motivation as mentioned in lines 394-399. For example, a key challenge in real-world interplanetary space mission trajectory design tasks (such as Cassini1-MINLP and Sagas) is the difficulty of directly evaluate the quality of trajectories. However, comparing different trajectories is inexpensive, accurate, and more feasible. On the other hand, these representative tasks show the complexity and diversity of the real-world scenarios, and the deployment of real-world experiments can better analysis the comprehensive and robust performance of our algorithm.

In the comparative experiments, RAPBO exhibits a performance trend that aligns with our expectations. During the early stages of optimization, its performance curve is similar to that of other methods. However, as other methods gradually converge, RAPBO continues to improve steadily and achieves the best results. As shown in Figure 4, this behavior is consistent with our analysis. In the early stages of optimization, the number of pairwise preferences available in the dataset is quite limited. As a result, our preference propagation technique cannot extract many preferential relations from the dataset, leading to similar performance between RAPBO and other methods. However, when the number of iterations reaches around 50, a sufficient number of pairwise preferences have been accumulated in the dataset. At this point, our preference propagation technique can play a more significant role, extracting more potential preferential relations from the dataset, thereby achieving relational augmentation of the dataset. This is the primary reason why RAPBO shows stable improvements during the later stages of optimization.

Thank you for your detailed review and valuable feedback on our work. We greatly appreciate your comments, particularly regarding the in-depth analysis of the propagation technique. We will carefully consider your suggestions to further improve the content of the paper. While we understand your concerns regarding some of the contributions, we are still grateful for your insights, which will help us enhance the quality of our work and lay a solid foundation for this research. Once again, thank you for your time and feedback.

Best regards