One step preference elicitation in multi-objective Bayesian optimization

Juan Ungredda, Jürgen Branke, Mariapia Marchi, Teresa MontroneGECCO Companion 2021 · DOI

TL;DR

This paper introduces a novel approach to multi-objective Bayesian optimization (BO) for expensive problems. Instead of having the decision-maker (DM) pick a solution after the optimization is complete, this method allows the DM to provide a single preference signal before the final optimization steps. This allows the BO algorithm to intelligently refine its search, leading to significantly better final solutions that better align with the DM's true preferences.

What Problem Does This Paper Address?

Many real-world problems involve optimizing multiple, conflicting objectives (e.g., maximizing performance while minimizing cost). When evaluating these objectives is computationally expensive, traditional multi-objective optimization methods struggle. A common approach is to generate a set of Pareto-optimal solutions (where no objective can be improved without worsening another) and let a decision-maker (DM) choose their preferred trade-off. However, for expensive problems, the number of evaluated solutions is limited, making it unlikely that the DM's truly preferred solution is even among the generated set. This paper addresses this gap by proposing a way to leverage a single preference input from the DM during the optimization process to guide the search towards more desirable solutions.

Methods

The core of the proposed method lies in integrating a "one-step" preference elicitation into a Bayesian Optimization framework, specifically using the ParEGO algorithm. Here's a breakdown:

  • Bayesian Optimization (BO): BO is ideal for expensive black-box functions. It builds a probabilistic model (typically a Gaussian Process) of the objective functions and uses an acquisition function to intelligently select the next point to evaluate, balancing exploration (discovering new areas) and exploitation (refining known good areas).
  • ParEGO: This is a multi-objective BO algorithm that uses a Tchebychev achievement scalarization function to convert the multi-objective problem into a single-objective one. It iteratively samples different scalarization weights to explore the Pareto front.
  • The Novelty: One-Step Preference Elicitation:
    1. Approximation and Elicitation: At a predetermined point before the end of the optimization budget (say, B - p evaluations), the algorithm uses the Gaussian Process models to generate a fine-grained, continuous approximation of the Pareto front.
  • DM's Single Input: The DM is presented with this approximated Pareto front and selects their most preferred solution (xp).
  • Preference Learning: The algorithm uses this single choice (xp) to infer the DM's underlying preferences. Assuming a Tchebychev utility function (which is consistent with ParEGO's internal workings), the algorithm estimates the parameters of this utility function.
  • Refined Search: The final p optimization steps then use this learned preference information (via the estimated utility function) to guide the acquisition function, focusing the search on the region predicted to contain the DM's most preferred solution.

Datasets

The paper evaluates its approach on three benchmark test functions:

  • HOLE function: A 2-objective function with variations (b > 0 and b = 0) to test different Pareto front shapes (discontinuous vs. continuous).
  • POL function: Another 2-objective function.

The authors do not introduce new benchmark datasets but use established ones to demonstrate the effectiveness of their method.

Key Insights and Ideas

  • Leveraging Intermediate Preferences: The most significant insight is that even a single preference signal from the DM during optimization can dramatically improve the final outcome, especially for expensive problems. This is a departure from traditional methods that require the DM to choose only at the very end.
  • The Power of Refined Search: By using the DM's preference to guide the final iterations, the algorithm can avoid getting "stuck" in suboptimal regions of the Pareto front and instead converge towards solutions that are genuinely more preferred by the DM.
  • Cognitive Load vs. Benefit: The authors argue that the cognitive burden on the DM is minimal (just picking one solution from a visual representation) compared to the substantial benefit in solution quality.
  • Trade-off in Elicitation Timing: There's a sweet spot for when to ask the DM. Asking too early might mean the approximated Pareto front is too inaccurate, leading to poor preference inference. Asking too late reduces the number of refinement steps. The paper empirically shows that asking around 80% of the way through the budget often yields the best results.

Key Results

  • Significant Improvement: The proposed "one-step preference elicitation" approach consistently found solutions with significantly higher DM utility compared to standard ParEGO (where the DM picks at the end) across all tested benchmark functions.
  • Robustness to Elicitation Timing: The benefit was observed for p=1 (one step before the end) and p=2 (two steps before the end), with p=1 often being sufficient.
  • Impact of Utility Model Mismatch: Even when the DM's true utility function was linear and the algorithm assumed a Tchebychev utility (a mismatch), the method still provided a benefit, though slightly less pronounced.
  • Budget Sensitivity: For a reduced budget (B=40), asking the DM closer to the end (p=1) was more beneficial than asking earlier, highlighting the importance of a sufficiently accurate Pareto front approximation.

Limitations and Future Work

  • Assumed Utility Function: The method assumes the DM's utility can be reasonably approximated by a Tchebychev function, especially when inferring parameters. While robust in experiments, a significant mismatch could theoretically impact performance.
  • Single Interaction: The current approach is limited to a single interaction. Future work could explore fully interactive approaches with multiple DM interactions during optimization.
  • Other BO Algorithms: The authors suggest exploring their preference elicitation idea with other Bayesian optimization algorithms beyond ParEGO.
  • More Complex Scenarios: Extending the approach to problems with more than two objectives or more complex DM preference models could be valuable.

Summary updated

BibTeX
@inproceedings{ungredda2021one,
  author = {Juan Ungredda and Jürgen Branke and Mariapia Marchi and Teresa Montrone},
  title = {{One step preference elicitation in multi-objective Bayesian optimization}},
  booktitle = {GECCO Companion},
  year = {2021},
  doi = {10.1145/3449726.3459515},
}
Figure