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:
- Clustering for Similarity: The algorithm employs a Gaussian Mixture Model (GMM) to identify clusters of similar solutions within the search space.
- 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).
- 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.
- 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.
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.
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