Technical Summary: DT-PBO – An Interpretable Tree-based Surrogate Model for Preferential Bayesian Optimization

1. Problem Statement

Preferential Bayesian Optimization (PBO) aims to identify a decision-maker's (DM) most preferred solution within a search space using the fewest possible pairwise comparisons (PCs). While existing PBO methods predominantly rely on Gaussian Process (GP) surrogates, these models suffer from a critical limitation: lack of interpretability. GPs function as black-box models, making it difficult for DMs to understand why certain solutions are preferred. This opacity is a significant barrier in high-stakes domains (e.g., healthcare, defense) where regulatory frameworks (such as the EU's GDPR) and ethical guidelines (e.g., NATO's responsible AI strategy) mandate explainability. Furthermore, post-hoc explanation methods for GPs are often unfaithful to the underlying model, potentially providing misleading insights.

The paper addresses the need for a surrogate model that is inherently interpretable while maintaining the ability to model preference uncertainty and support active learning (sample efficiency).

2. Methodology: DT-PBO

The authors propose DT-PBO, a novel Decision Tree (DT) based surrogate model designed specifically for PBO. Unlike standard decision trees trained on classification or ranking data, DT-PBO learns directly from pairwise comparison data. The method follows the standard PBO optimization loop (Figure 1) but replaces the GP surrogate with a tree-based structure.

2.1 Partitioning the Space (Splitting Heuristic)

The core innovation is a Consistency Score splitting heuristic designed to partition the feature space based on observed preferences rather than ranking labels.

• Mechanism: For a node $A$ containing a set of comparisons $D_A$, the algorithm evaluates candidate splits (feature index $k$ and threshold $t$).
• Consistency Score ($S_A$): A split is scored based on how well it separates "winners" from "losers." Specifically, it calculates the empirical mean of a variable $Z_i(s)$, which is $+1$ if the winner is on one side of the split and the loser on the other, $-1$ if reversed, and $0$ if both are on the same side. The score is the absolute value of this mean.
• Straddler Exclusion: A key structural feature is the exclusion of "straddlers" (pairs where one item falls in the left child and the other in the right) from the datasets used for descendant splits. The authors argue mathematically that straddlers contain no information about the internal structure of the child nodes once the parent split is established. This exclusion naturally controls tree growth, favoring shallow, interpretable trees without requiring aggressive hyperparameter tuning.

2.2 Leaf Parameter Estimation

Once the tree structure is determined, the model assigns a probabilistic estimate to each leaf to support active learning.

• Probabilistic Leaves: Instead of a single value, each leaf $j$ is modeled as a Gaussian distribution with mean $f_j$.
• Laplace Approximation (LA): The authors employ a Bayesian approach where the latent utility values across leaves follow a joint multivariate Gaussian prior. They use Laplace Approximation to find the Maximum A Posteriori (MAP) estimate and the posterior covariance.
• Identifiability: To resolve the translational invariance inherent in pairwise likelihoods (where adding a constant to all utilities does not change preferences), a sum-to-zero constraint ($\sum f_i = 0$) is applied. This ensures the model is identifiable and removes irreducible variance in the constant-shift direction.
• Hyperparameters: The model relies on the ratio of noise variance to prior variance ($\sigma^2_{noise}/\sigma^2_{prior}$), which is shown to be the only identifiable parameter governing the optimization.

2.3 Active Learning

The model utilizes the qEUBO (Expected Utility of Best Option) acquisition function to select the next most informative pairwise comparison.

• Inter-leaf vs. Intra-leaf: While qEUBO effectively selects comparisons between different leaves, it collapses within a single leaf (where the predictive mean is constant). To address this, the authors employ a heuristic for within-leaf prioritization in discrete settings, focusing exploration on the leaf currently believed to contain the optimum.

3. Key Contributions

1. Tree-based Preference Learning: The development of an algorithm that learns interpretable decision trees directly from pairwise comparison data using a novel consistency-based splitting heuristic and probabilistic leaf estimation.
2. Numerical Evaluation: Empirical verification showing that DT-PBO achieves competitive convergence to state-of-the-art GP-based models (SkewGP and LA-based GP), particularly on functions with rugged optimization landscapes (e.g., De Jong, Holder, Schwefel). The method demonstrates significantly faster computational running times (10–400x faster than GPs).
3. Real-life Case Studies: Demonstration of the model's interpretability and utility in two distinct scenarios:
   • Sushi Preferences: Showing the model can recover user preferences and generalize to unseen items.
   • Patient Message Ranking (PMR): A high-stakes clinical triage task where the model identifies specific features (e.g., "red flag syndrome," "message actionability") driving urgency, providing insights opaque to black-box LLM or GP approaches.

4. Results

• Convergence: Across eight benchmark functions, DT-PBO performs competitively. It slightly underperforms on smooth, non-rugged functions (e.g., Rosenbrock, Hartmann) but outperforms or matches GPs on rugged functions.
• Efficiency: DT-PBO is computationally superior, with running times of ~12 seconds for 200 iterations compared to hundreds or thousands of seconds for GP variants. This is attributed to the avoidance of hyperparameter optimization for kernel lengthscales and the reduction of the Hessian matrix size from the number of unique items ($m$) to the number of leaves ($m_l$).
• Robustness: The model is robust to noise in preferences and insensitive to small changes in the noise/prior ratio hyperparameter.
• Interpretability: In case studies, the resulting trees (depth 4–6) provide clear, human-readable rules (e.g., "If chest pain is present, prioritize") that align with domain knowledge, unlike the black-box outputs of GPs or Large Language Models (LLMs).

5. Significance and Limitations

The paper claims that DT-PBO offers a viable, inherently interpretable alternative to black-box GP surrogates in PBO. Its significance lies in bridging the gap between sample-efficient optimization and the need for explainability in critical decision-making domains. By providing transparent models, it allows decision-makers to refine their preferences with greater confidence and trust.

Limitations acknowledged by the authors:

• Indifference: The current model cannot explicitly model indifference statements ($A \sim B$).
• High Dimensions: Performance degrades on non-rugged functions as dimensionality increases ($D > 7$), likely due to the axis-aligned nature of decision tree splits struggling with complex, diagonal decision boundaries common in high-dimensional smooth functions.
• Feature Extraction: In the PMR case study, the quality of the final model depends on the reliability of the LLM used for feature extraction.

The authors conclude that while limitations exist, DT-PBO successfully demonstrates that interpretable surrogate models can achieve competitive performance in PBO, particularly in scenarios where interpretability is a prerequisite for deployment.