Preferential Bayesian Optimization

Start with the figure below. It shows two colors and asks which you prefer. Answer a dozen times, honestly, and watch the curve underneath: it is the model's estimate of how much you like each hue, with a band for how unsure it is, and the star is its current guess at your favorite. You never typed a number. Every answer was a choice between two options, and the system decided which two to show you next.

That loop is preferential Bayesian optimization (PBO). Chapter 18 built its first half: a Gaussian process utility that learns from comparisons. This chapter builds the second half, the rule for choosing the next comparison, and then looks at what happens when the loop runs. The ideas carry over from Chapter 11 with one change that turns out to matter a great deal: a query is now a pair of inputs, and the answer is one bit.

19.1 The problem #

There is a latent utility $g$ on a domain $\X$: how much a person likes each option. We want an input with high utility,

but $g$ cannot be evaluated. What can be done is to show the person two options, $\vx$ and $\vx'$, and record which one they choose. Following Chapter 16, the answer is random, with a probability that grows with the utility difference:

where $\vx \succ \vx'$ reads "$\vx$ is preferred to $\vx'$", $\Phi$ is the standard normal CDF, and $\sigma$ is the noise in the person's evaluation of each option. The logistic link $1/(1 + e^{-(g(\vx) - g(\vx'))/\tau})$ of the Bradley-Terry model is used just as often; the choice between them matters for theory (Chapter 21) more than for the loop in this chapter.

The budget is small. A person can answer perhaps a few dozen comparisons in a session before fatigue sets in, and Chapter 32 shows that many real sessions end much sooner. At the end the system must recommend one option, usually the one with the highest posterior mean utility.

Three things make this harder than ordinary Bayesian optimization. Each answer carries at most one bit, far less than a measured value. The answer says nothing about the absolute level of $g$, only about differences, so utilities are identified up to a shift (Section 18.4). And the query has twice as many inputs, so choosing it means searching over pairs.

19.2 The dueling formulation #

The name preferential Bayesian optimization comes from González et al. (2017), who posed the problem in a way that avoids the latent utility altogether. They modeled the preference function $\pi(\vx, \vx') = \Prob(\vx \succ \vx')$ directly, as a Gaussian process classifier on the product space $\X \times \X$ of pairs, which they called the dueling space, with a logistic link.

Without a utility, "the best option" needs a definition that uses only pairwise probabilities. They used the Condorcet winner: an option that beats every other option with probability above one half. It may not exist when preferences are not transitive, so they scored each option by its soft-Copeland value, the average probability that it wins against a uniformly random opponent,

and sought its maximizer. If preferences do come from a utility as in Equation (19.1), the soft-Copeland maximizer is the utility maximizer, because $\pi(\vx, \vx')$ increases with $g(\vx)$ for every opponent.

They proposed three acquisition functions. Pure exploration picks the duel whose outcome is most uncertain. Copeland expected improvement looks one step ahead at the soft-Copeland value. Dueling Thompson sampling draws one sample of the preference function, takes the option with the best soft-Copeland score under that sample as the first member of the duel, and pairs it with the option whose duel against it is most uncertain. On one- and two-dimensional test functions, discretized to 33 points per dimension, with 5 initial and 200 further duels over 20 repetitions, dueling Thompson sampling was consistently the best strategy; Copeland expected improvement over-exploited and was expensive enough that they ran it only on one function, and the dueling-bandit baseline needed about 4000 iterations to approach what Thompson sampling reached in 200 (González et al., 2017).

The dueling space doubles the input dimension and puts an integral inside every evaluation of the objective, which is part of why most later work went back to the latent-utility model of Chu and Ghahramani (2005) that Chapter 18 develops, and why the default implementation in BoTorch is built on it (Balandat et al., 2020). The rest of this chapter uses that model. The two views agree when preferences come from a utility; Chapter 21 returns to what the dueling view buys when they do not.

19.3 Choosing a pair #

With a posterior over the utility in hand, the question is which pair to show. A good pair usually has two jobs. One option should be a strong candidate, so that the answer refines what we know near the top. The other should be a challenger whose comparison with the first is genuinely uncertain, so that the answer teaches something. A pair of two obviously bad options, or of a strong option against an obviously worse one, wastes a question.

The first rules followed this recipe literally. Brochu et al. (2007) took the best option shown so far, by posterior mean, as the first member, and as the second the option with the highest expected improvement over it, the acquisition function of Section 12.3 applied to the latent utility. The maximally uncertain challenge of Fauvel and Chalk (2021) keeps the same champion and picks the challenger whose duel outcome has the largest epistemic variance, the part of the outcome's uncertainty that more data would remove. The hallucination believer of Takeno et al. (2023) draws one sample of the latent comparison values from the posterior, treats it as data, and then applies any standard acquisition function to the resulting Gaussian process.

These rules work, but four independent groups reported the same weakness of the expected-improvement family: it stalls. Expected improvement of a challenger over a well-known champion is small, so the rule stops testing the champion, learns only how the challengers compare with one another, and never learns whether any of them beats the incumbent (González et al., 2017; Fauvel and Chalk, 2021; Takeno et al., 2023; Astudillo et al., 2023). That is an inference from the four reports rather than a result any one of them proves (inference); Astudillo et al. (2023) do prove the stall for the batch version, below.

19.4 Expected utility of the best option #

A cleaner rule comes from asking what the comparison is for. Suppose the session ended right after this query and we recommended whichever of the two options the person picked. If their answer is reliable, they pick the one with the higher utility, and the value of the query is the utility of the better of the two. We do not know $g$, so we take its expectation under the posterior:

the expected utility of the best option, where $\E_n$ is the expectation under the posterior after $n$ comparisons. EUBO was introduced for preference exploration in multi-objective problems (Lin et al., 2022) and generalized to queries of $q$ options, $\E_n[\max_i g(\vx_i)]$, under the name qEUBO (Astudillo et al., 2023).

Under the Laplace approximation of Section 18.2, the posterior values $A = g(\vx_1)$ and $B = g(\vx_2)$ are jointly Gaussian, so Equation (19.2) has a closed form.

The formula shows how one expression does both jobs from Section 19.3. The first two terms are a weighted average of the two means, large when either option is good. The last term grows with $s$, the uncertainty about which option is better. Exploitation and exploration appear in one formula with no tuning constant. Three properties are worth checking against the figure below:

• A pair of identical options is worth one option: $s = 0$ and $\EUBO(\vx, \vx) = \mu(\vx)$.
• A pair is never worth less than its better mean: $\EUBO \ge \max\{\mu_A, \mu_B\}$, by Jensen's inequality.
• At fixed means, EUBO increases with $s$ (Exercise 19.1).

The heatmap makes the trade-off visible. After five duels the model cannot tell whether the wide bump near $x = 0.25$ or the region near $x = 0.7$ is better, and EUBO asks exactly that question: its maximum pairs a point from each. Pressing Ask the next pair a few times shows the map sharpening as the answers come in.

19.4.1 What is known about EUBO #

EUBO is more than a plausible heuristic. A query's one-step Bayes optimal value is the best expected utility of the final recommendation achievable after one more answer; an acquisition function that maximizes it is the knowledge gradient of Section 12.6. Lin et al. (2022) proved that EUBO is one-step Bayes optimal for preference exploration. Astudillo et al. (2023) extended the analysis to $q$ options:

• With noise-free answers, a maximizer of qEUBO is one-step Bayes optimal, so qEUBO coincides with the knowledge gradient.
• With logistic noise of scale $\tau$ (Equation (16.4)), the one-step value of qEUBO's choice is at most $\tau\, W\!\left((q-1)/e\right)$ below the optimum, where $W$ is the Lambert W function, the inverse of $w \mapsto we^w$.
• On a finite domain with $q = 2$ and further technical conditions, the Bayesian simple regret of qEUBO decays faster than $1/n$.
• Under the same assumptions, a batch version of expected improvement, qEI, can have simple regret bounded away from zero for every $n$: it is not asymptotically consistent. This is the stall from Section 19.3, now proved.

The third result assumes a finite set of options, which makes it an identification problem; it does not compare directly with the rates for continuous domains in Chapter 21 (inference). In BoTorch, the analytic EUBO and qEUBO are available with the PairwiseGP model; qEUBO arrived in version 0.10.0 in February 2024 (Meta Platforms, Inc., 2026e).

19.5 A complete loop #

Putting the pieces together gives the algorithm that runs inside Figure 19.1.

The figure below runs the same loop against a simulated person with a hidden favorite hue, so you can check the model against a known answer.

Some things to try. With the default noise, EUBO usually puts the star within a few degrees of the hidden favorite after ten to fifteen answers. Random pairs get there more slowly and less reliably, because many random pairs compare two mediocre hues. Raise the noise to 0.5 and the curve flattens: the model reads inconsistent answers as small utility differences, exactly as Equation (19.1) says it should. For some seeds, EUBO stops a little short of the favorite and keeps asking about nearly the same pair; that is the first failure mode below.

19.5.1 More than one parameter #

A hue is one number. Real designs have many: a typeface has weight, width, contrast, and slant; an exoskeleton controller has timing and torque for each phase of the stride. Nothing in Algorithm 19.1 depends on the dimension, but the amount the model must learn does. The figure below runs the same loop over generated designs with 3, 6, or 10 parameters: background hue, corner roundness, shape size, then saturation, stripes, rotation, and so on.

Two things stand out in the recorded curves. The first is the cost of dimension. When EUBO chooses the pairs, forty comparisons close about two thirds of the gap to the favorite with three parameters, about 40 percent with six, and about 30 percent with ten. Each comparison still carries at most one bit, while the space it must locate the favorite in grows with every parameter. Learning a person's taste over ten parameters from a few dozen choices is a different problem from learning it over one, and Chapter 30 follows that problem into the research literature.

The second is that, in this simple implementation, choosing pairs by EUBO is not better than choosing them at random once the first twenty or so answers are in. With three and six parameters the EUBO curves flatten after about twenty answers while the random curves keep falling: after forty answers, random pairs have closed about 87 percent of the gap with three parameters and about half of it with six. With ten parameters the two medians are within about 0.05 of each other from twenty answers on, and both rules close about 30 percent. The mechanism is visible if you watch the pairs: EUBO keeps proposing two designs near the current best guess, so the answers refine a small region and stop testing the rest. That is the collapse reported for EUBO in the failure modes below, here amplified by searching a small candidate set (inference). The simulated photo sessions of Section 25.4.1 show the opposite ordering, with EUBO pairs well ahead of random ones, under a different setup: six adjustments of a real photograph, only pairs at least 0.2 apart, and a recommendation restricted to compared settings. Both simulations search a candidate pool that includes perturbations of the best guesses, so the pool is not the difference; we have not separated which of the others accounts for the reversal (inference). It is a reminder that an acquisition function's guarantees concern one step under the model's assumptions, and that whether it beats random pairs over a whole session is an empirical question, one that has rarely been asked with people (Section 28.9).

19.6 Known failure modes #

The loop above is close to what practitioners run: a Gaussian process preference model with the probit link and the Laplace approximation, and EUBO or qEUBO to choose queries. Between 2024 and 2026 several groups examined it closely and found problems. Most of these reports are preprints, so they should be read as findings to be confirmed rather than settled results.

EUBO collapses toward the current best. Wu and Gardner (2026) derived the exact knowledge gradient under the probit likelihood in closed form, showed that EUBO is a lower bound on it, and on a two-dimensional test function showed EUBO's queries gathering around the estimated maximum, while the exact knowledge gradient kept exploring. Under noise, the equivalence of EUBO and the knowledge gradient no longer holds, and the gap is where the collapse comes from.

The comparison graph falls apart. Think of every compared input as a node and every answered pair as an edge. Shao et al. (2026) observe that EUBO tends to choose new pairs that share no input with earlier queries, so each pair is an isolated edge, and the likelihood Hessian in the Laplace approximation becomes rank deficient. Section 18.5 explains why connectivity matters for any comparison model, and reports the correction the authors propose and its size.

Good final answers can hide a costly path. On samples from a Gaussian process, Xu et al. (2024b) reported that qEUBO's recommended solution was slightly better than their optimistic algorithm's, but its cumulative regret, which counts the utility of everything shown along the way, was more than 2.5 times higher. Which number matters depends on whether the person has to live with the options they are shown.

Older rules have their own failures. Thompson sampling over-explores as the dimension grows, and the hallucination believer, which does best at very low noise, can get stuck when answers are noisy (Takeno et al., 2023; Xu et al., 2024b).

Chapter 28 collects these results with the conditions under which each was observed, and Chapter 27 looks at the inference side of the same pipeline.

19.7 When the oracle is a person #

The simulated person in Figure 19.3 has a fixed utility, constant noise, and unlimited patience. You do not, and neither does anyone in the studies of Chapter 32 and Chapter 33. Go back to Figure 19.1 and answer another twenty questions. Did you ever choose against your own earlier answers? Did the colors you liked change as you saw more of them? Did you start to like the hue the star was pointing at partly because the system kept showing it to you?

These are not hypothetical worries. In a three-month field deployment of a human-in-the-loop optimizer, 415 of 549 evaluation sequences stopped at the first iteration (Ou et al., 2022). When an optimizer rather than the person leads the search, people tend to reach better designs while reporting less agency over them (Chan et al., 2022; Niwa et al., 2025). Whether repeated comparisons find a preference or partly make one is the question Part IX takes up, and the experiment that would separate the two, randomizing the order of queries and retesting a week later, is described in Section 47.4. The algorithm of this chapter is the right starting point; the people it runs on are the reason the book continues past it.

19.8 Exercises #

Further reading #

• González et al. (2017) define the problem, the dueling space, and the soft-Copeland score; Brochu et al. (2007) is the earlier gallery-based formulation for material design.
• Chu and Ghahramani (2005) is the preference model this chapter builds on.
• Lin et al. (2022) introduce EUBO and prove its one-step optimality; Astudillo et al. (2023) give qEUBO, its noisy-answer bound, and the inconsistency of qEI.
• Takeno et al. (2023) study the inference behind the loop and propose the hallucination believer; Wu and Gardner (2026) and Shao et al. (2026) are the 2026 preprints on EUBO's failure modes.
• BoTorch's preference tutorial runs this chapter's loop with PairwiseGP and EUBO (Meta Platforms, Inc., 2026c).