Relation-Augmented Dueling Bayesian Optimization via Preference Propagation

Xiang Xia, Xiang Shu, Shuo Liu, Yiyi Zhu, Yijie Zhou, Weiye Wang, Bingdong Li, Hong QianIJCAI 2025 · DOI · OpenReview

Abstract

Dueling Bayesian Optimization (DBO) is a powerful tool for optimizing systems where only relative preferences (A is better than B) are available. However, traditional DBO methods often suffer from data inefficiency because they treat each pairwise comparison in isolation. We present Relation-Augmented Dueling Bayesian Optimization (RADBO), a framework that leverages Gaussian Mixture Models (GMM) and directed hypergraphs to propagate preferences across similar solutions. By uncovering hidden relationships in the data, RADBO significantly improves convergence rates and outperforms existing state-of-the-art preference-based optimization methods.

Introduction

In many complex engineering domains—such as tuning robotic gaits, designing aerodynamic car cabins, or optimizing spacecraft trajectories—obtaining an absolute numerical score for a candidate solution is often prohibitively expensive or technically impossible. In these scenarios, researchers turn to Dueling Bayesian Optimization (DBO), which relies on simple A/B comparisons (e.g., "Design A is preferred over Design B").

Despite its utility, the primary bottleneck in DBO is data inefficiency. Most existing algorithms fail to exploit the underlying structure of the solution space. For instance, if solution A is preferred over B, and B is known to be very similar to C, it is highly probable that A is also preferred over C. Current methods overlook these transitive relationships, leading to slow convergence and high evaluation costs.

Methodology: Preference Propagation via Hypergraphs

RADBO addresses the inefficiency of DBO by introducing a "Preference Propagation" step that artificially expands the available dataset through relation augmentation. The process follows four key stages:

  1. Clustering for Similarity: The algorithm employs a Gaussian Mixture Model (GMM) to identify clusters of similar solutions within the search space.
  2. Relation Augmentation: Using the identified clusters, RADBO constructs directed hypergraphs. Unlike standard graphs that connect individual nodes, hypergraphs connect sets of solutions. Specifically, it categorizes solutions into three sets: bad (those defeated by the similar set), similar, and good (those that defeat the similar set).
  3. Transitive Propagation: By applying the principle of transitivity (if $A \succ B$ and $B \approx C$, then $A \succ C$), RADBO generates "augmented" preferences. This allows the model to "hallucinate" accurate comparisons without requiring additional, expensive real-world evaluations.
  4. Efficient Modeling: The use of hypergraphs reduces algorithmic complexity from quadratic ($O(n^2)$) to linear ($O(m)$) relative to the number of hyperedges, ensuring the framework remains scalable.
Conceptual overview of RADBO: The left panel shows isolated standard preferences, while the right panel illustrates how hypergraphs propagate preferences through clusters of similar solutions.

These augmented preferences are integrated into a Gaussian Process (GP) surrogate model, which guides the selection of the next pair of solutions via Dueling-Thompson Sampling.

Experimental Results

RADBO was evaluated against 18 synthetic benchmark functions and several high-dimensional real-world tasks, including RobotPush (14D) and Carcab design (7D).

Performance on Synthetic Benchmarks

Across a variety of multimodal and convex landscapes, RADBO consistently demonstrated superior accuracy and faster convergence compared to state-of-the-art methods like PBO, KSS, and qEUBO. In benchmarks such as the Griewank function, RADBO identified optimal regions significantly earlier in the optimization process.

Performance comparison of RADBO against baseline methods across six standard synthetic optimization benchmarks. RADBO (blue line) consistently achieves higher 'Best-so-far' values more quickly.

Real-World Impact and the "Cost Ratio"

A critical finding of this research is the relationship between evaluation costs and optimization strategy. The study demonstrates that when evaluating a direct function value is 1.5 to 2.5 times more expensive than performing a pairwise comparison, RADBO becomes more efficient than traditional value-based Bayesian Optimization (like GP-UCB). This makes RADBO a highly practical choice for expensive engineering simulations.

Conclusion and Future Work

RADBO represents a significant advancement in preference-based optimization by successfully bridging the gap between isolated data points using solution similarity. While the empirical results are robust, future work will focus on providing formal theoretical proofs for convergence rates and exploring adaptive clustering techniques to further refine the preference propagation logic. By treating preferences as a web of interconnected relations rather than isolated events, RADBO sets a new standard for efficient, high-dimensional dueling optimization.

Summary updated

Abstract

In black-box optimization, when directly evaluating the function values of solutions is very costly or infeasible, access to the objective function is often limited to comparing pairs of solutions, which yields dueling black-box optimization. Dueling optimization is solely based on pairwise preferences, and thus notably reduces cost compared with function value based methods. However, the optimization performance of dueling optimization is often limited due to that most existing dueling optimization methods do not make full use of the pairwise preferences collected. To better utilize these preferences, this paper proposes relation-augmented dueling Bayesian optimization (RADBO) via preference propagation. By considering solution similarity, RADBO aims to uncover the potential dueling relations between solutions within different preferences through the proposed preference propagation technique. Specifically, RADBO first clusters solutions using a Gaussian mixture model. After obtaining the solution set with the highest intra-cluster similarity, RADBO utilizes a directed hypergraph to model the potential dueling relations between solutions, thereby realizing relation augmentation. Extensive experiments are conducted on both synthetic functions and real-world tasks such as motion control, car cab design and spacecraft trajectory optimization. The experimental results disclose the satisfactory accuracy of augmented preferences in RADBO, and show the superiority of RADBO compared with existing dueling optimization methods. Notably, it is verified that, under the same evaluation cost budget, RADBO can be competitive with or even surpass the function value based Bayesian optimization methods with respect to optimization performance.
BibTeX
@inproceedings{xia2025relation,
  author = {Xiang Xia and Xiang Shu and Shuo Liu and Yiyi Zhu and Yijie Zhou and Weiye Wang and Bingdong Li and Hong Qian},
  title = {{Relation-Augmented Dueling Bayesian Optimization via Preference Propagation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/740},
}
Figure