Source-linked AI summary
Preferential Bayesian Optimization
Javier Gonzalez, Zhenwen Dai, Andreas Damianou, Neil D. Lawrence
TL;DR
The paper addresses black-box optimization when objective values are unavailable and only pairwise preference feedback can be obtained. It introduces Preferential Bayesian Optimization, which models duel outcomes with a Gaussian process and Bernoulli likelihood and selects comparisons through adapted acquisition functions. Experiments report superior performance for PBO, particularly DTS, while the method assumes a specified latent duel-reward relationship and some acquisition variants can be computationally demanding.
Problem
The problem is to find the minimum of a latent black-box function using binary preferences from pairwise duels instead of direct function queries.
Method
Preferential Bayesian Optimization models duel preferences with a Gaussian process and Bernoulli likelihood, then selects comparisons through acquisition policies over the duel space.
Results
PBO-DTS shows superior performance in simulations, balancing exploration and exploitation in the duel space and outperforming alternatives such as IBO and other bandit methods.
Takeaways & Limitations
Modeling correlations across points enables non-greedy selection of relevant comparisons and supports efficient preferential optimization.
Takeaways & Limitations
The framework assumes duel rewards follow f([x, x′]) = g(x′) − g(x), while other preference-reward relationships are possible.
Abstract
from arXiv · showhide
Bayesian optimization (BO) has emerged during the last few years as an effective approach to optimizing black-box functions where direct queries of the objective are expensive. In this paper we consider the case where direct access to the function is not possible, but information about user preferences is. Such scenarios arise in problems where human preferences are modeled, such as A/B tests or recommender systems. We present a new framework for this scenario that we call Preferential Bayesian Optimization (PBO) which allows us to find the optimum of a latent function that can only be queried through pairwise comparisons, the so-called duels. PBO extends the applicability of standard BO ideas and generalizes previous discrete dueling approaches by modeling the probability of the winner of each duel by means of a Gaussian process model with a Bernoulli likelihood. The latent preference function is used to define a family of acquisition functions that extend usual policies used in BO. We illustrate the benefits of PBO in a variety of experiments, showing that PBO needs drastically fewer comparisons for finding the optimum. According to our experiments, the way of modeling correlations in PBO is key in obtaining this advantage.
1. Introduction
The paper introduces optimization through pairwise preferences when the black-box objective cannot be queried directly. It proposes a Gaussian-process preference model and acquisition policies to select informative comparisons.
- Problem: The objective is a bounded black-box function whose minimum must be found using as few pairwise duels as possible.Each duel returns binary feedback indicating which of two points is preferred, rather than either function value.
- Problem: This setting differs from standard Bayesian optimization because direct feedback from the objective is unavailable.The objective is accessed only through indirect observations of preferences.
- Motivation: Preference-based optimization is relevant to applications such as web-design A/B testing and recommender systems.The motivation also reflects settings where people evaluate differences more readily than absolute magnitudes.
- Related work: Prior work includes dueling-bandit methods, noisy comparisons, contextual preferences, and Gaussian-process preference learning.Existing Gaussian-process approaches extend acquisition functions such as Expected Improvement to choose new duels.
- Contribution: The proposed approach learns a preference function over duels with a Gaussian process to capture correlations across the domain and select comparisons non-greedily.The paper presents this as combining strengths of bandit methods with probabilistic modeling of domain correlations.
- Paper scope: The paper develops latent-preference modeling, generalized dueling acquisition functions, comparative experiments, and concluding discussion.The sections cover preference concepts and learning, acquisition policies, experiments, and future research.
2. Learning latent preferences
The paper learns latent pairwise preferences with a Bernoulli model and Gaussian-process inference, then identifies the optimum through the soft-Copeland score. Correlations across duels support data-efficient learning, while numerical integration and optimization recover the most likely optimum.
- Preference model: The objective is accessed only through binary duel outcomes indicating which of two inputs is preferred.The unobserved joint reward is modeled as f([x, x′]) = g(x′) − g(x), with feedback y ∈ {0, 1}.
- Preference model: A preference function maps each duel to the probability that the left input wins, with reversed inputs having complementary probabilities.The logistic inverse link is πf([x, x′]) = σ(f([x, x′])).
- Soft-Copeland optimization: The soft-Copeland score integrates pairwise win probabilities over the input space, providing a smooth measure of how likely each point is to win duels.A Condorcet winner is defined as the point with maximal soft-Copeland score.
- Soft-Copeland optimization: A Condorcet winner under the soft-Copeland score is a global minimum of the latent objective, so optimization reduces to finding that winner from duel observations.This connection follows because the preference reward is positive against every competing point only at a minimum of f.
- Gaussian-process inference: Gaussian-process classification infers the latent preference function from duel data while modeling correlations across duels.The posterior is analytically intractable and requires approximation, but correlation modeling can make the approach more data efficient than bandit scenarios.
- Optimization procedure: Monte Carlo integration with uniformly selected landmark points approximates the soft-Copeland score, after which numerical optimization computes the most likely optimum.The estimated Condorcet winner maximizes the average probability of winning duels given the observed dataset.
3. Sequential Learning of the Condorcet winner
The paper develops sequential duel-selection policies for identifying the Condorcet winner when the latent objective is accessible only through pairwise comparisons. It contrasts pure exploration and Copeland Expected Improvement with dueling-Thompson sampling, which balances exploration and exploitation while selecting both duel locations.
- Sequential duel selection: The sequential policy chooses additional duels to identify the latent function's minimum as quickly as possible, while the acquisition search space is X × X rather than X.The best current estimate of the optimum is the Condorcet winner.
- Acquisition functions: The framework proposes pure exploration, Copeland Expected Improvement, and dueling-Thompson sampling as acquisition functions for pairwise optimization.These methods represent different exploration–exploitation strategies in the duel space.
- 3.1. Pure Exploration: Pure exploration selects duels with high uncertainty in the GP-transformed outcome probability, because Bernoulli outcome variance can remain high after repeated observations.The alternative GP-based uncertainty measure captures epistemic uncertainty about the latent preference function; the associated integral is approximated with Monte Carlo.
- 3.2. Copeland Expected Improvement: Copeland Expected Improvement weights the possible improvement from each duel outcome by its probability and selects the pair maximizing this expected gain.The two outcomes correspond to either duel participant winning, with probabilities given by the preference model.
- 3.3. Dueling-Thompson sampling: Copeland Expected Improvement is computationally demanding and can over-exploit, whereas dueling-Thompson sampling is designed to be fast and explicitly balance exploration with exploitation.Dueling-Thompson sampling first samples a preference function to choose a likely Condorcet winner, then selects the opponent using outcome-probability uncertainty in that direction.
- 3.3. Dueling-Thompson sampling: With more evaluations, Thompson sampling increasingly favors the current Condorcet winner, while multiple simultaneous comparisons require generalized acquisition functions.The multiple-comparison setting is equivalent to pairwise preference modeling but differs in how the locations to rank are selected.
4. Experiments
The experiments evaluate PBO on four benchmark objectives using pairwise comparisons and show that PBO-DTS generally outperforms the alternatives, while correlation modeling accelerates optimization over bandit methods.
- Correlation modeling: PBO-DTS can make a good initial guess with five random duels, whereas Sparring must visit each of 900 arms before improving.Figure 6 compares the methods on the Six-Hump Camel over a horizon of 4000 bandit iterations.
- Experimental setup: The experiments optimize four benchmark functions on a 33^q grid using five initial duels, a 200-duel budget, and 20 trials.The benchmarks are Forrester, Six-Hump Camel, Goldstein, and Levy; performance is the objective value at the current Condorcet winner.
- Compared methods: Six methods are compared: PBO-PE, PBO-CEI, PBO-DTS, RAMDOM, IBO, and bandit methods.The PBO variants represent pure exploration, Copeland Expected Improvement, and dueling Thompson sampling.
- Results: PBO-DTS is consistently the best policy, balancing exploration and exploitation in the duel space.PBO-CEI tends to overexploit, while PBO-PE tends to perform worse in larger dimensions.
- Results: Bandit methods require many more evaluations to converge because they do not model correlations across arms.Their performance is especially affected as the number of arms, and therefore the dimension, increases.
5. Conclusions
The paper introduces PBO for optimizing black-box functions accessible only through preferences and proposes duel-specific acquisition policies. Its simulations identify DTS as the strongest practical policy, while the approach remains limited by input-space dimensionality.
- Contribution: PBO models pairwise comparisons of black-box points with a Gaussian process and defines acquisition policies for selecting informative duels.The proposed policies are PE, CEI, and DTS.
- Findings: DTS shows superior performance because it balances exploration and exploitation in the duel space while remaining computationally tractable.The conclusion reports state-of-the-art performance against IBO and other bandit methods in simulation.
- Limitation: The current approach is limited by input-space dimensionality, which doubles relative to the original problem when correlations among duels are modeled.The authors identify further theoretical analysis of the proposed acquisitions as future work.