Preferential Multi-Objective Bayesian Optimization
Authors: Raul Astudillo
Kejun Li
Maegan Tucker
Chu Xin Cheng
Aaron Ames
Yisong Yue
Venue: Accepted by TMLR ()

Abstract: Preferential Bayesian optimization (PBO) is a framework for optimizing a decision-maker’s latent preferences over available design choices.  While real-world problems often involve multiple conflicting objectives, existing PBO methods assume that preferences can be encoded by a single objective function. For instance, in the customization of robotic assistive devices, technicians aim to maximize user comfort while minimizing energy consumption to extend battery life. Likewise, in autonomous driving policy design, stakeholders must evaluate safety and performance trade-offs before committing to a policy. To bridge this gap, we introduce the first framework for PBO with multiple objectives. Within this framework, we propose dueling scalarized Thompson sampling (DSTS), a multi-objective generalization of the popular dueling Thompson sampling algorithm, which may also be of independent interest beyond our setting. We evaluate DSTS across four synthetic test functions and two simulated tasks—exoskeleton personalization and driving policy design—demonstrating that it outperforms several benchmarks. Finally, we prove that DSTS is asymptotically consistent. Along the way, we provide, to our knowledge, the first convergence guarantee for dueling Thompson sampling in single-objective PBO.

Published in Transactions on Machine Learning Research (05/2025)
Preferential Multi-Objective Bayesian Optimization
Raul Astudillo'
rastudilccallech. edu kh5&@caltech. edu mntucker@gaten edu Baltechh edu omes@caltedd edu yyue edu
Kejun Li"
Maegan Tucker2
Chu Xin Cheng
Aaron D. Ames
Yisong Yuc!
California Institade of Technology
Georgia Instibute of Technology
Reviewed on OpenReview: https: /ttp://ppppe openreview. net/ forun? id= d=mjsoESaWDH
Abstract
Preferential Bayesian optimization (PBO) a framework for optimizing a decision-maker's latent preferences over available design choices. While real-world problems often involve multiple conflicting objectives, existing PBO methods assume that preferences can be encoded by single objective function. For instance, in the customization of robolic assistive devices, technicians aim to maximize user comfort while minimizing energy consumption to extend battery life. Likewise, in autonomous driving policy design, stakeholders must evaluate safety and performance trade-offs before committing to a policy. To bridge this gap, we introduce the first framework for PBO with multiple objectives. Within this framework, we propose dueling scalorized Thompson sampling (DSTS), a multi-objective generalization of the popular dueling Thompson sampling algorithm, which may also be of independent interest beyond our setting. We evaluate DSTS across four synthetic test functions and two simulated tasks cxxsklleton personalization and driving policy design-demonstee demonstrating that it outperforms several benchmarks. Finally, we prove that DSTS is asymptotically consistent. Along the way, we provide, to our knowledge, the first convergence guarantee for dueling Thompson sampling in objeeveobjective PBO.
1 Introduction
Bayesian optimization (BO) a framework for optimizing objective functions with expensive or time- consuming evaluations. Tt has been successful in real-world applications such as hyperparameter tuning of machine learning algorithms (Snoek al. 2012), e-commerce platform design (Letham & Bakshy 2019). and materials design (Zhang al. 2020 Preferential Bayesian optimization (PBO), subframework within BO, focuses on settings where the objective function is latent, i.e., where the objective values cannot be observed and instead, only ordinal preference feedback from a decision- maker (DM) is observed.
While prior work in PBO has demonstrated success in various applications (Brochu et al., 2010 Nielsen et al. 2015 Tucker al., 2020bb, existing methods operate under the assumption that preferences can be encoded by single objective function. In practice, however, problems are often characterized by multiple conflicting objectives. This occurs, for instance, when multiple users with conflicting preferences collaborate in joint design task, as illustrated in Figure [ or when user wishes to explore the trade-offs between multiple conflicting attributes before committing to design.
To motivate the need for multi-objective PBO, we examine two illustrative applications. The first application involves an exoskeleton customization task that aims to enhance user comfort. In this situation, a user assisted by an cxoskeleton experiences different gait designs and indicates the most comfortable option (Tucker) et al. 2020a|b). In this and other robotic assistive personalization applications, users and clinical technicians often collaborate design task to maximize comfort (the user's objective) while optimizing energy

---

Published in Transactions on Machine Learning Research (05/2025)
Pareto Front
"I prefer A fi(A) > /1(B)
"I prefer B fz(B) f2(A)
Objective 1 (h)
A
B
Objective (f2)
Figure 1: In this work, we extend preferential Bayesian optimization to the multi-objective sctting. In contrast with existing approaches, our approach allows the decision-makers involved in the joint design task efficiently explore optimal trade-offs between the conflicting objectives.
consumption and other metrics related the exoskeleton's 's long-tern ang-term functionality (the technician's 's objective)
[Kedrraon al. 2021
The second application is autonomous driving policy design, where user is presented with multiple simulations of an autonomous vehicle under different driving policies, and the user indicates the one with better safety and performance attributes (Biyik et. al.] 2019). In such settings, policy-makers often seek to understand the tradc-offs between multiple latent objectives, such as lane keeping and speed tracking, before committing to a specific policy (Bhatia et al., 2020).
Motivated by the applications described above, we propose framework for PBO with multiple objectives. Our contributions are as follows:
To the best of our knowledge, our work proposes the first framework for preferential Bayesian optimization with multiple objectives.
We present dueling scalarized Thompson sampling (DSTS), the first extension of dueling Thompson
sampling (DTS) algorithms Sui et al. 2017 Novoseller al. 2020 Siivola et al. 2021 to the multi-objective setting.
We prove that DSTS is asymptotically consistent. Furthermore, we also provide the first convergence guarantee for DTS in single-objective PBO.
We demonstrate our framework across six test problems, including simulated exoskeleton personaliza- tion and autonomous driving policy design tasks. Our results show that DSTS can efficiently explore the objectives' Pareto front using preference feodback.
2 Related work
2.1 Preference-basee optimization
Creserence-based optimization has been actively studied across various frameworks, including multi-armed bandits (Yue et al. 2012 Bengs et al.) 2021), reinforcement learning (Wirth et al. 2017). and BО (Brochu
et al. 2010: González et al.
2017 Astudillo et al. 2023). It has been successful in a broad range of applications,
such as personalized medicine NNelsen et al. 2015 Sui et al. 2017 Tucker et al.
2020a robot control (Biyik 2022) and, more recently, the 2021 Maccarini et al.] 2022: Csomay-Shanklin et al.
et al. 2019 Tucker et. al.
alignment of large language models (Rafailov et al. 2023).
Most work in this area focuses on the single-objective setting. Two notable exceptions are the works of (Bhatia et al. 2020 and (Zhou et al. 2023). Bhatia et. al. 20200 considers one-shot, preference-basedd optimization
2

---

Published in Transactions on Machine Learning Research (05/2025)
across multiple criteria over a finite design space. This study adopts a game-theoretic viewpoint and introduces the concept of a Blackwell winner, which implicitly requires the user to specify acceptable trade-off between criteria, in contrast with our work. (Zhou et al., 2023) considers multi-objective preference alignment of large language models. Like our work, these two works are motivated by the idea that preferenco-based optimization across multiple objectives is crucial for capluring richer human leedback.
Our work extends the dueling Thompson sampling algorithm for dueling bandits introduced by (Sui et al, 2017] (termed self-sparring). which has been adapted to preference- breeeeence-baee reinforcement learning (termed dueling posterior sampling) (Novoseller et al. 2020) and PBO (termed batch Thompson sampling) (Siivola
ct al. 2021) To our knowledge, we provide the first multi-objective generalization of this algorithm.
2.2
Multi-objective optimization
The field of multi-objective optimization has been extensively studied, encompassing both theoretical advancements and applications across various engineering problems (Miettinen 1999 Marler & Arora 2004
Deb 2013). Litcrature within the BO framework most closcly related to our work (Khan et al., 2002
Knowles 2006
Belakaria al. 2019 Paria et al. 2020
Daulton al. 2020).
Our algorithm draws inspiration from ParEGO Knowles 2006 multi-objective BO algorithm that employs augmented Chebyshev scalarizations to convert a multi-objective optimization problem into multiple single- objective problems. Unlike Knowles (006). our objectives are not observable, preventing direct modeling of scalarized values, Instead, we model each objective separately and scalarize samples drawn from these models, similar to Daulton ct al. (2020 's version of ParEGO.
Additionally; our work is related to research that incorporates user preferences into multi-objective optimiza- tion topic that has been actively studied both within and beyond the BO framework (Branke & Deb 2005) Wang et al. 2017 Hakanen & Knowles 2017 Lin et al., 2022). In most of this prior work, all objectives are assumed to be directly observable, and user preferences are captured through a latent utility function that combines these objectives into a single score to guide optimization. In contrast, we do not assume access to the objective values. Instead, we receive binary preference feedback for each objective individually, without ever observing their actual values or requiring predefined utility function aggregate them.
2.3 Additional related work
Emerging from the operations research community, the field of multi-criteria decision analysis (MCDA) focuses decision-making under multiple conflicting criteria (Keeney & Raiffa 1993 Pomerol & Barba-Romero
2000 Although our work is related to this field, it diverges from the traditional MCDA approaches, which
often involve aggregating preferences across criteria into a single performance measure (Young) 1974 Dyer & Sarin 1979: Baskin & Krishnamurthi 2009 Bhatia et al., 2020p. Such aggregation requires additional assumptions about the DM's desired trade-off. Additionally, methods in this field have been explored outside the PBO framework, making them not directly applicable in our setting.
3 Problem setting
Preferences Let X denote the space of designs. We assume there is a DM (which may represent one multiple users collaborating on design task) aiming to maximize their preferences over designs. We assume the DM's preferences can be encoded via m objective functions fm X + R so that, for any given pair of designs x, E X, the DM prefers x over x' with respect to objective and only if fy(z) > fz()). For simplicity, we assume all m objectives are latent, but our approach can be easily adapted to settings where some objectives are observable, as discussed in Section
Goal Let f = [f....., fm] : X + " denote the concatenation of the m objective functions. The DM seeks to find designs that maximize each objective. This concept is formalized through the notion Pareto-dominance. For a pair of designs x, x' E X, x Pareto-dominatee x', denoted by > x', if fa()) 2 f/()") for j I.....m m with strict inequality for at least one index j. The DM seeks to find the Pareto-optimal set of f, defined by
3

---

Published in Transactions on Machine Learning Research (05/2025)
x; (x: x' such that x' y x}. The set (f(x): x3} is termed the Pareto front of f. Figure 2 depicts the Pareto front for one of our test problems; the light grey region is the set of feasible objective vectors, i.., (f(x) : I E ] and the dark grey curve indicates the Pareto front of f.
Feedback To assist the DM's goal, our algorithm collects preference feedback interactively (Algorithm) ! At each iteration, denoted by ,,...,, .N, the algorithm selects query constituted of q designs X, (In,11...,,xx. X The DM then indicates their most preferred design among these q designs for each objective. Let rj.n E (1.....q) denote the DM's preferred design with respect to objective j. The collection of these responses is denoted by In ( Tm,.n m)
0.0
Feasible region
Algorithm Ducling Scalarized Thompson Sampling
Input Initial dataset: Pu, and prior on f: Po-
-0.5
for = .....NN do
Compute Pr. the posterior on f given Dn-1
Sample On uniformly at random over à
-1.0
Draw samples fn.1....n.q. ~ Pn Find Zn,s E argmax s ((n,; ( i= 1=1.....9 Set X,, (In.1....,, ,n,g)) and observe I' Update dataset D,, Dn (()n:a))
iid
-1.5
-1.5
-1.0
-0.5
0.0
y1
end for
Figure 2: Feasible region and Pareto front of the DTL.72 test function.
4 Dueling scalarized Thompson sampling
We introduce a novel algorithı termed dueling scalarized Thompson sampling (DSTS), summarized Algorithm [ DSTS is obtained by adeptly combining ideas from preference-based and multi-objective optimization derive a sound algorithm with strong performance and convergence guarantees. As common in BO, our algorithm is comprised of probabilistic model of the objective functions for predictions and uncertainty reasoning, along with sampling policy that, informed by the probabilistic model, iteratively selects new queries, balancing exploration and exploitation.
4.1 Probabilistic model
The probabilistic model is encoded by prior distribution over S, denoted by Pa- We assume Po consists of a set of independent Gaussian processes, each corresponding to an objective. However, our framework does not rely on this choice and can casily accommodate other priors as long as samples from the postcrior dist ribbutinn can be drawn.
As is standard in the PBO literature (González et al. 2017 Nguyen al. 2021 Astudillo et al. 2023). we account for noise in the DM's responses by using Logistic likelihood for each objective j === =,..., of the following form:
exp(A)(em.)/AN) P =() _x_
1=
(1)
where by > 0 is the noise-level parameter. We estimate X, along with the other hyperparameters via maximum likelihood. We assume noise is independent across objectives and interactions.
Let. Do denote the initial dataset and Dn-1 Do U {(X,, rx)) denote the data available right before the n-th interaction with the DM. Let P., denote he posterior over f given Dn-1- The posterior cannot be computed in closed form but can be approximated using, e.g., a variational inducing point approach (Nguyen ct al. p021p. For observable objectives, the above model can be replaced by a standard Gaussian process model with Gaussian likelihood (see Appendix B.1
4

---

Published in Transactions on Machine Learning Research (05/2025)
4.2
Sampling policy
Our primary algorithmic contribution is our sampling policy, which extends the dueling Thompson sampling (DTS) algorithmic family to the multi-objective setting. This is achieved by leveraging augmented Chebyshev scalarizations, a technique from multi-objective optimization used to decompose a multi-objoctive optimization problem into multiple single-objective problems. We next explain augmented Chebyshev scalarizations and describe how we integrate them with DTS.
Augmented Chebyshev scalarizations Augmented Chebyshev scalarizations are widely used for multi- objective optimization (Miettinen 1999). In BO, in particular, they were employed by Knowles (0066 and
Paria et al. (2020). We also leverage them to derive sound sampling policy in our setting.
For given vector of scalarization parameters, 0 E : the augmented Chebyshev scalarization function is defined by
= {0 E R" E== Og = and 0, 2 0, j = 1.......... m),
syy: min {0,2) + Σ 0,83. j=l...., m
(2)
where is a small positive constant. It can be shown that any solution of maX s (f(x); 0) lies in the Parcto-optimal set of f. Conversely, if p is small enough, every point in the Parcto-optimal set of f is a solution of maxxex s (f))));) for some 0 E θ (Theorem 3.4.6, Miettinen 1999).
Ducling scalarized Thompson sampling At cach iteration, n, we draw sample from the scalarization parameters uniformly at random over θ denoted by 0n. We also draw independent samples, denoted by fh.,...,,f.., from the posterior distribution on f given Dn-1- The next query is then given by Xn = (Fn.1....,In.o)) where
Tn,s E argmax s (fn)(z);8n,, i == 1......
3)
=EX
Intuitively, our sampling policy operates by first determining subset of the Pareto-optimal set of f using on. denoted as x y:d.. argmax,ex zex {(f(r);;,) Then, each FnZs is sampled according to the probability (induced by the posterior on f) that Fn E X f:O.² analogous to single-objective dueling posterior sampling (Sui el al. 2017). The DM's responses provide information of the highest value point among Fn.1y..., Tn.o for each objective, which in turn allows us to learn about X f:O.. Since 0₂ is drawn independently at each iteration, we explore diverse collection of subsets j within Xj.
We note that our sampling policy is agnostic to the choice of the probabilistic model, provided that samples from the posterior can be drawn. In addition, our sampling policy is suitable for problems with mixed latent and observable objectives thanks to its dual interpretation a policy for preference- based optimization (Sui 2017) and traditional optimization with observable objectives (Paria et al. 2020 Specifically, when
et al.
all objectives are observable, our sampling policy can be interpreted as a batch generalization (Kandasamy
ct al. 2018 of the scalarized Thompson sampling algorithm proposed by Paria et al. 2020
4.3 Theoretical analysis
We now study the convergence properties of DSTS. We begin by analyzing the single-objective setting and establish the asymptotic consistency of DTS. To our knowledge, this is the first such result for DTS in PBO. The result is stated in Theorem [ with a proof based on a martingale argument provided in Appendix (A22
Theorem 1. Suppose that X is finite, m = 1, and the sequence of queries { is chosen according to the DTS policy. Then, for each x E X, limm-+oc Pn(x E argmax,'xx f(x)) = 1(x E argmaxgexflel almost surely for f drawn from the prior.
Extending this result to the multi-objective sctting requires a minor modification to the DSTS algorithm. Specifically, our proof introduces small probability of comparing against fixed reference design in each iteration. This modification is required by our proof due to the non-linear nature of Chebyshev scalarizations
5

---

Published in Transactions on Machine Learning Research (05/2025)
0.40
225
150000
hypervolume
hypervolume
hypervolume
200
0.30
140000
Random PBO-DTS-IF
0.25
175
dPrEEGO
QEHVI
0.20
150
oMES
130000
DSTS
125
0
50
100
0
50
100
0
50
100
number of queries
number of queries
number of queries
(a) DTLLI
(b) DTLZ2
(c) Vehicle Safety
0.08
350
0.06
hypervolume
hypervolume
nypervolums
300
0.04
250
0.00
50
100
100
50
100
number queries
number queries
number of queries
(d) Car Side Impact
(e) Autonomous Driving
(f) Exoskeleton
Figure 3: Our framework was demonstrated on six test problems: DTLZ1 (a), DTLZ2 (b), Vehicle Safety (c), Car Side Impact (d), Autonomous Driving (c), and Exoskcleton (f). Overall, proposed method (DSTS) delivers the best performance. qMES and qParEGO exhibit mixed performance, achieving good results in some test problems and poor results in others. The remaining methods, Random, PBO-DTS-IF, and qEHVI, consistently underperform DSTS.
and is required in the single-objective case. The resulting convergence guarantee is stated in Theorem 2 The proof-whiee be found in Appendix A.3 again relies martingale argument and the fact that varying 0 allows Chebyshev scalarizations to recover all Pareto-optimal points.
Before stating the result, we describe the modified DSTS policy under consideration. Assume q= 2, and fix any reference point Fref E X and E (0, 1). At each iteration, the first design #a,1 is selected as in Equation while the second design 2n set to Fref with probability ò, or otherwise selected via Equation
Theorem 2. Suppose that is finite, q == 2, and the sequence of queries {Xn is chosen according to the modified DSTS policy described above. Then, for each X, lim P, (x E X7) 1(x e xX²) almost surely for f drawn from the prior.
We now place our results in context with prior theoretical work DTS. Sui al. 2017) showed that DTS achieves asymptotic consistency and sublinear regret in the dueling bandits setting, assuming independent pairs of arms. However, their analysis does not extend to setting, where may be correlated. Notably, the analysis of Sui et al. (2017) relics on showing that all arms are chosen infinitely often, which may not be true in our context. Similarly, Novoseller el al. 2020) showed analogous convergence results in reinforcement. learning setting under a Bayesian linear reward model. In contrast, our result holds for non-linear objectives. Morcover, the result. of Novoseller al. (2020) also relics on showing that cach arm is selected infinitely often. Finally, note that the results of Sui et al. (2017) and Novoseller et al. (2020) are only applicable in the single-objective setting; discussed above, the multi-objective setting presents additional challenges.

---

Published in Transactions on Machine Learning Research (05/2025)
Unlike prior work, do not establish regret bounds for DSTS. Indeed, such bounds remain open question even for DTS in single-objective PBO. While we see this as a valuable research direction, such analysis is beyond the scope of our work which primarily aims to introduce multi-obeective PBO. Finally, it is important to recognize that the asymptotic consistency of data-driven algorithms like DSTS cannot be taken for granted. For instance, Astudillo et al. (2023) showed that the adaptation of qEI proposed by [iivola et al. (2021) is not asymptotically consistent and can perform poorly singlc-objective PBO, despite being one of the most widely used algorithms. In Theorem 3 we show that qEHVI (Daulton et al., 2020), a multi-objective
generalization of qEI, suffers from the same limitation in setting. A proof is provided in Appendix A.4 Our empirical results support this finding, showing that qEHVT can perform very poorly.
Theorem 3. There crists problem instance with finite X and q 2 such that if Xn E argmaxxexx Xex (XH for all n, then lim Pn(x E Xj) almost surely for some flxd E X and m (0,,))
5 Numerical experiments
We evaluate our algorithm across six test problems and compare it with five other sampling policies. All algorithms are implemented using BoTorch (Balandat et al. 2020). Details on the performance metric, the benchmark sampling policies, and the test problems are provided below. The code for reproducing our experiments can found at https: cww cot////auuAusuuuuoooo/o////
5.1 Performance metric
We quantify performance using the hypervolume indicator, which has been shown to result in good coverage of Parcto fronts when maximized /Zitzler et al., 2003). Let Y" = (ye i be a finite approximation of the [r.
Pareto front of f. Its hypervolume given by HV((",r) = (r. vector, μ denotes the Lebesgue mcasure over R", and [r. ye] denotes the hyper-roctangle bounded by the vertices and yt- We report performance by setting 4 equal to the set of Pareto optimal points across designs shown to the DM.
where r E R is a reference
5.2 Benchmarks
We compare our algorithm (DSTS) against uniform random sampling (Random), three adapted algorithms from standard multi-objective BO (qParEgo, qEHVI, qMES), and a standard PBO algorithm with inconsistent overall preference feedback (PBO-DTS-IF). Our experiments in this section use the regular version of DSTS. In Appendix B.3 we show that the modified version of DSTS used in Theorem 2 achieves virtually the same performance for small values of 5. All algorithms use the same priors, and the resulting posteriors are approximated via the variational inducing point approach proposed by Nguyen et al. (2021). Approximate samples from the posterior distribution used by DSTS and PBO-DTS-IF are obtained via 1000 random Fourier features (Rahimi & Recht 2007).
Adapted standard multi-objective BO methods common approach in the PBO literature is to use a batch acquisition function designed for parallel BO with observable objectives, ignoring the fact that preference feedback observed rather than objective values (Sivoola et al. 2021 Takeno al. 2023). Despite lacking the principled interpretations they enjoy in their original setting, they often deliver strong empirical performance. Following this principle, adopt three batch acquisition functions from standard multi-objective BO benchmarks: qParEGO (Knowles) 2006 Daulton et al. 2020), qEHVI (Daulton et al. 2020), and qMES [Belakaria et al.) 2019). Since these algorithms were not originally designed for latent objectives, they require minor adaptations that we describe in Appendix [B5] These algorithms use the same probabilistic model as DSTS. Thus, any difference in performance is solely due to the use different sampling policies.
Singlc-objective PBO with inconsistent aggregated preference feodback Single-objcctive PBO methods are often applied to problems characterized by multiple conflicting objectives. In such cases, DMs are expected to aggregate their preferences across objectives, which be challenging for DMs and often
7

---

Published in Transactions on Machine Learning Research (05/2025)
(a) Autonomous Driving
(b) Exoskeleton Walking
Figure 4: Simulation environments used in test problems.
results in inconsistent feedback. For example, in the context of exoskeleton personalization, this would require forcing the exoskeleton user and clinical technician to reach unified response at every iteration, which be challenging if the user's objective is to maximize comfort while the technician's objective is to ensure the exoskeleton's 's long-term energy efficiency. To understand the effect of using this approach, we include a standard single-objective PBO approach using inconsistent feedback. Additional details on this benchmark are provided in Appendix B.5
0.0
0.0
0.0
Fessitle region
Fessible region front PBC-OTS-IF
Feusible region Parato frant yParEGO
Random
-0.5
-0.5
-0.5
V/2
-1.0
-1.0
-1.0
-1.5
-1.5
-1.5
-1.5
-1.0
-0.5
0.0
-1.5
-1.0
-0.5
0.0
-1.5
-1.0
-0.5
0.0
Vi
V1
V1
(a) Random
(b) PRO-DTS-IF
(c) qParEGGO
0.0
0.0
Feasitle region
Fessibl ragion
Feasible region
GEHVI
oMES
DSTS
-0.5
-055
-0.5
-1.0
-1.0
-1.5
-1.5
-1.5
-1.5
-1.0
-0.5
0.0
-1.5
-1.0
-0.5
0.0
-1.5
-1.0
-0.5
Vi
V1
V1
(d) qEHVI
(e) qMES
(f) DSTS
Figure 5: Illustration of sampled designs for the DTLZ2 function. These figures show that our proposed method (DSTS) provides better exploration of the Pareto front than its competitors.
5.3
Test problems
We report performance across four synthetic test problems (DTLZ1, DTLZ2, Vehicle Safety, and Car Side Impact), a simulated autonomous driving policy design task (Autonomous Driving), and simulated exoskeleton gait design task (Exoskeleton) using queries with q = 2 and q = 4 designs. Details of these test problems provided below. In all problems, initial dataset is obtained using 2(d 1) queries chosen
8

---

Published in Transactions on Machine Learning Research (05/2025)
uniformly at random over X where d is the input dimension of the problem. After this initial stage, cach algorithm was used to select. 100 additional queries sequentially. Results for g 2 are shown in Figure 3 Each plot shows the mean of the hypervolume of the designs included in queries thus far, plus and minus 1.96 times the standard error. Each experiment was replicated 30 times using different initial datasets. In all problems, the DM's responses are corrupted by moderate levels of Gumbel noise, which consistent. with the use of a Logistic likelihood (sce Appondix B.2 for the details). Results for q = can be found in Appendix B.4
DTLZ1 and DTLZ2 The DTLZI and DTLZ2 functions are standard test problems from the multi- objective optimization literature (Deb et al. design variables and m = 2 objectives, and DTLZ2 with d = design variables and m = 2 objectives. Results for these problems are shown in Figures 3(a) and 3(b) respectively. Our approach achieves the best performance in both problems, tied with qParEGO on DTLZ2.
2005). In our experiments, we configure DTLZI with d = 6
Surprisingly, on the DTLZ2 problem, PBO-DTS-IF, qEHVI, and qMES underperform significantly, even being surpassed by Random. To understand this, we plot a representative set of objective vectors corresponding to the queried designs in Figure 5 As illustrated, Random offers reasonable exploration of the Pareto front (likely due to the low dimensionality of DTT.22).. However, it exposes the user to many low-quality designs, which can potentially frustrate DMs. PBO-DTS-IF and qMES tend to favor designs where one of the objectives achieves its maximum possible value, which may be problematic for DMs sceking more balanced solutions. qEHVT fails to explore the Pareto front, concentrating its queries on a limited sub-optimal region instead. Finally, DSTS and qParEGO provide a more comprehensive exploration of the Pareto front.
Vehicle Safety and Car Side Impact. The Vehicle Safely and Car Side Imppcc test functions are designed to emulate various metrics of interest in the context of crashworthiness vehicle design. Overall, these test problems emulate an expert's assessment based on expensive experiments where cars are intentionally crashed, and safety metrics are evaluated. Vehicle Safety has d = 5 design variables and m = 3 objectives. Car Side Impact has d = 7 design variables and m objectives. For further details, we refer the reader to Tanabc & Ishibuchi (020). Results for the Vehicle Safety and Car Side Impact experiments can be found in Figures 3(() and (dd) respectively. For the Vehicle Safety problem, qMES is the best-performing algorithm, followed by DSTS. For the Car Side Impact, DSTS performs the best, followed closely by qMES.
Autonomous Driving Policy Design To supplement the synthetic test functions, we further evaluate our algorithm on a simulated autonomous driving policy design task. For this problem, we use a modification of the Driver enviroument presented in Biyik et al. (2019). A similar euvironment was also used by Bhatia et al. (2020), providing empirical evidence that user preferences in this context are inherently governed by multiple latent objectives. In our modified environment, illustrated in Figure [[a] an autonomous control policy is created to drive a trailing (red) vehicle forward to goal location while maintaining some minimum distance with leading (white) vehicle. The control policy switches between two modes, collision avoidance and goal-following, based on a minimum distance threshold. The behavior of the leading car is fixed by
setting a pre-specified set of actions.
Using this simulation environment, we consider four objectives representing approximations of subjective notions of safety and performance: lane keeping, speod tracking, heading angle, and collision avoidance. The design space is parameterized by four control variables: two parameters that account for how fast the vehicle approaches the goal or the other vehicle, respectively, one position gain that accounts for the adjustment the desired heading, and the minimum distance threshold used to switch between the two modes. The results of this experiment are shown in Figure 3(e) As illustrated, our approach again delivers better performance than its competitors.
Exoskeleton Gait Customization Lastly, we evaluate our algorithm on an exoskeleton gail personalization task using a high-fidelity simulator of the lower- body exoskeleton Atalante (Kedrroon et al. 2021), illustrated in Figure 4(b) This problem emulates the scenario discussed in the introduction, in which there are two conflicting objectives: subjective user comfort and energy efficiency. For simulation purposes, we approximate comfort as linear combination of three attributes: average walking speed (faster speed is preferred),
9

---

Published in Transactions on Machine Learning Research (05/2025)
maximum pelvis acceleration (lower peak acceleration is preferred), and the center of mass tracking error (lower error is preferred). We approximate total energy consumption as the I--norm of joint-level torques, averaged over the simulation duration. We note that this is an observable objective. Thus, our approach is modified as discussed in Section f and further claborated on Appendix B.1 to leverage direct observations of this objective.
The design space is parameterized by five gait features: step length, minimum center of mass position with respect to stance foot in sagittal and coronal plane, minimum foot clearance, and the percentage of the gait cycle at which minimum foot clearance is enforced. Each unique set of features corresponds to unique gait. These gaits are synthesized using the FROST toolbox (Hereid & Ames 2017) and are simulated in Mujoco to obtain the corresponding objectives. Since simulations are time-consuming, we build surrogate objectives by fitting a (regular) Gaussian process to the objectives obtained from 1000 simulations, with each set of gait features drawn uniformly over the design space. As shown Figure 3(f) DSTS achieves the best. performance, followed closcly by qParEGO and qMES.
5.4 Discussion
Across the broad range of problems considered, DSTS delivers the best overall performance. Specifically, DSTS yields the highest hypervolume in nearly all problems (except for the Vehicle Safety problem, where it is second to qMES). Two of the standard multi-objective benchmarks, qParEGO and qMES, exhibit mixed results, highlighting the importance of developing algorithms designed handle preference feedback as opposed naively adapting algorithms intended for observable objectives. Notably, qEHVI the worst-performing algorithm, even surpassed by Random. This is consistent with Thcorem 3 which shows that qEHVT is not consistent in general, thus highlighting the value of our asymptotic consistency result for DSTS (Theorem 2 Lastly, PBO-DTS-IF consistently underperforms DSTS, confirming that single-objective PBO approach is insufficient to explore the optimal trade-offs in problems with multiple conflicting objectives. The runtimes of all methods are discussed in Appendix B.6
6 Conclusion
In this work, we proposed a framework for PBO with multiple latent objectives, whore the goal is to help DMs efficiently explore the objectives' Pareto front guided by preference feedback. Within this framework, we introduced dueling scalarized Thompson sampling (DSTS), which, to our knowledge, the first approach for PBO with multiple objectives. Our experiments demonstrate that DSTS provides significantly better exploration of the Pareto front than several benchmarks across six test problems, including simulated autonomous driving policy design and exoskeleton gait customization tasks. Moreover, we showed that DSTS is asymptotically consistent, providing the first convergence result for ducling Thompson sampling in PBO.
While our work provides a sound approach to tackling important applications not covered by existing methods, there are also a few limitations that suggest avenues for future exploration. Future work could include a deeper thcoretical analysis of DSTS, such as investigating convergence rates and regret bounds, as well the development. of alternative sampling policies. For example, Astudillo et al. (2023) provided an efficient. approach to approximate one-step lookahead Bayes optimal policy in single-objective PBO, demonstrating superior performance against various established benchmarks. Although their approach cannot be casily adapted to our context, exploring alternative mechanisms for computing non-myopic sampling policies in our setting would be valuable. Finally, it would be interesting to explore DSTS in other settings, such as preference-basee based reinforcement learning.
Acknowledgments
This research was partially supported by Wandercraft.
10

---

Published in Transactions on Machine Learning Research (05/2025)
References
Raul Astudillo, Zhiyuan Jerry Lin, Eytan Bakshy, and Peter Frazier. qEUBO: A function for preferential Bayesian optimization. In International Conference on Artificial Intelligence and Statislics, pp. 1093 1114. PMLR, 2023.
acquisition
Maximilian Balandat, Brian Karrer, Daniel Jiang, Samuel Daulton, Ben Letham, Andrew G Wilson, and Eytan Bakshy, Botorch: A framework for efficient monte-carlo Bayesian optimization. Advances in neural information processing systems, 33:21524-21538, 2020.
Jacob Baskin and Shriram Krishnamurthi. Preference aggregation in group recommender systems for committee decision-making In Proceedings of the Third ACM Conference on Recommender Systems, pp- 337-340, 2009.
Syrine Belakaria, Aryan Deshwal, and Janardhan Rao Doppa. Max-value entropy search for multi-objective Bayesian optimization. Advances in Newral Information Processing Systems, 32, 2019.
Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi-Paul, and Eyke Hüllermeier. Preference-based online learning with dueling bandits: A survey, The Journal of Machine Learning Research, 22(1):278- 385, 2021.
Kush Bhatia, Ashwin Pananjady, Peter Bartlett, Anca Dragan, and Martin J Wainwright. Preference learning along multiple criteria: A game-theoretic perspective. Advances in newral information processing systems, 33:7413 7424, 2020.
Erdem Bıyık, Malayandi Palan, Nicholas Landolfi, Dylan P Losey, and Dorsa Sadigh. Asking easy questions: A frienfriendly approach active reward learning. arXiv preprint arXiv:1910.0 04365, 2019.
Jürgen Branke and Kalyanmoy Deb. Integrating user preferences into evolutionary multi-objective optimization. Knowledge Incorporation in Evolutionary Computation, pp. 461-477. Springer, 2005.
Eric Brochu, Tyson Brochu, and Nando De Freitas. A Bayesian interactive optimization approach to procedural animation design. In Proceedings of the 2010 ACM SICCRAPHH/Barogppplee Symposium Computer Animation, pp. 103-112, 2010.
Nocl Csomay-Shanklng Maegan Tucker, Min Dai, Jenna Reher, and Aaron D Ames. Learning controller gains on bipedal walking robots via user preferences. In 2022 International Conference on Robolics and Automation (ICRA), pp.
IEEE, 2022.
Samuel Daulton, Maximilian Balandat, and Eytan Bakshy. Differentiable expected hypervolume improvement for parallel multi-objective Bayesian optimization. Advances in Neural Information Processing Systems, 33: 9851 9864, 2020.
Kalyanmoy Deb. Multi-objective optimization. In Search Methodologies: Introductory Tutorials in Optimiza- tion and Decision Support Techniques, pp. 403-449. Springer, 2013.
Kalyanmoy Deb, Lothar Thiele, Marco Laumanns, and Eckart Zitzler. Scalable test problems for evolutionary multiobjective optimization. In Evolutionary Multiobjeclãve Oplimizalion, pp. 105-145. Springer, 2005. doi:
10.1007/1184422-1131 137-7 6.
Joseph Doob. Application of the theory of martingales. Le calcul des probubilites et ses applications, pp. 23-27, 1949.
James S Dyer and Rakesh Sarin. Group preference aggregation rules based on strength of preference. Munagement Science, (5()))822 832, 1979.
Javier González, Zhenwen Dai, Andreas Damianou, and Neil D Lawrence. Preferential Bayesian optimization. In International Conference on Machine Learning, pp. 1282-1291. PMLR, 2017.
Jussi Hakanen and Joshua D Knowles. On using decision maker preferences with ParEGO. In Evolutionary Multi- Criterion Oplimization, pp. Springer, 2017.
11

---

Published in Transactions on Machine Learning Research (05/2025)
Ayonga Hereid and Aaron D Ames. FROST: Fast robot optimization and simulation toolkit. In 2017 IEEF/RSJ International Conference on Intelligent Robots and Systems, pp. 719-726. IERE, 2017.
Kirthevasan Kandasamy, Akshay Krishnamurthy, Jeff Schneider, and Barnabas Poczos. Parallelised Bayesian optimisation via Thompson sampling. In Amos Storkey and Fernando Perez-Cruz (eds.), Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pp. 133-142. PMLR, 09-11 Apr 2018.
Ralph L Keeney and Howard Raiffa. Decisions with multiple objectives: preferences and value trade-offs.
Cambridge university press, 1993.
Jacques Kerdraon, Jean Gabriel Previnaire, Maegan Tucker, Pauline Coignard, Willy Allegre, Emmanuel Knappen, and Aaron Ames. Evaluation of safety and performance of the self balancing walking system atalante in patients with complete motor spinal cord injury. Spinal cord series and cases, 7(1):71, 2021.
Nazan Khan, David E Goldberg, and Martin Pelikan. Multi-objective Bayesian optimization algorithm. In Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation, pp. 684-684, 2002.
Joshua Knowles. ParEGO: A hybrid algorithm with on-line landscape approximation for expensive multiob- jective optimization problems. IEEE Transactions on Evolutionary Computation, 10(1))50-66, 2006.
Benjammin Letham and Eytan Bakshy. Bayesian optimization for policy search via online-offline experimentation. J. Mach. Learn. Res., 20:145-1, 2019.
Zhiyuan Jerry Lin, Raul Astudillo, Peter Frazier, and Eytan Bakshy. Preference exploration for efficient Bayesian optimization with multiple outcomes. In International Conference Artificial Intelligence and Statistics, pp. 4235-4258. PMIRR, 2022.
Marco Maccarini, Filippo Pura, Dario Piga, Loris Roveda, Lorenzo Mantovani, and Francesco Braghin. Preference-based optimization of a human-robot collaborative controller. IFAC-PapersOnIiing 55(38):7-12, 2022.
R Timothy Marler and Jasbir Arora. Survey of multi-objective optimization methods for engincering. Structural and Multidisciplinary Oplimization, 26:369 395, 2004.
Kaisa Micttinen. Nonlincar multiobjective optimization. International Scries in Operations Research & Management Science. Springer, 1999.
Quoc Phong Nguyen, Scbastian Tay, Bryan Kian Hsiang Low, and Patrick Jaillet. Top-k ranking Bayesian oplimization. In Proceedings of the AAAI Conference on Arlificial Intelligence, volume 35, pp. 9135 9143, 2021.
Jens Brehm Bagger Nielsen, Jakob Nielsen, and Jan Larsen. Perception-based personalization of hearing aids using Gaussian processes and active learning. JEEE/ACM Transactions on Audio, Speech, and Language Processing, 23(1):162 173, 2015.
Ellen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick. Dueling posterior sampling for preference-basee reinforcement learning. In Conference on Uncertainty in Artificial Intelligence, pp. 1029-1038. PMLR, 2020.
Biswajit Paria, Kirthevasan Kandasamy, and Barnabás Póczos. A flexible framework for multi-objective Bayesian optimization using random scalarizations. In Uncertainty in Artificial Intelligence, pp. 766-776. PMLR, 2020.
Jean-Charles Pomerol and Sergio Barba-Romero Multicriterion decision in management: principles and practice, volume 25. Springer Science & Business Media, 2000.
Rafacl Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. In seirth- Conference on Newaal Information Processing Systems, 2023.
12

---

Published in Transactions on Machine Learning Research (05/2025)
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in Newral Information Processing Systems, 20, 2007.
Carl Edward Rasmussen and Christopher K Williams. Gaussian processes for machine learning. MIT Press, 2006.
Eero Siivola, Akash Kumar Dhaka, Michael Riis Andersen, Javier González, Pablo García Moreno, and Aki Vehtari. Preferential batch Bayesian optimization. In 2021 IEEE 31st International Workshop on Machine Learning for Signal Processing, pp. 1 6. IEEE, 2021.
Jasper Snock, Hugo Larochelle, and Ryan P Adams. Practical Bayesian optimization of machine learning algorithms. Advances in neural information processing systems, 25, 2012.
Yanan Sui, Vincent Zhuang, Joel W Burdick, and Yisong Yuc. Multi-ducling bandits with dependent arms. arxiv preprinl arxiv 705.70000000 00253, 2017.
Shion Takeno, Masahiro Nomura, and Masayuki Karasuyama. Towards practical preferential Bayesian optimization with skew Gaussian processes. In Andreas Krause, Emmna Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 33516-33533. PMLR, 23 29 Jul 2023.
Ryoji Tanabe and Hisao Ishibuchi. An casy-to-use real-world multi-objective optimization problem suite. Applied Soft Compuling, 89:106078, 2020.
Maegan Tucker, Myra Cheng, Ellen Novoseller, Richard Cheng, Yisong Yue, Joel W Burdick, and Aaron D Ames. Human preference-based learning for high-dimensional optimization of exoskeleton walking gaits. In 2020 IEEE/RS RSJ International Conference on Intelligent Robots and Systems, pp. 3423 3430. IEEE 2020a.
Maegan Tucker, Ellen Novoseller, Claudia Kann, Yanan Sui, Yisong Yue, Joel W Burdick, and Aaron D Ames. breserence-based learning for exoskeleton gait optimization. In 2020 IEEE International Conference on Robolics and Aulomalion, pp. 2351 2211. IEEE, 2020b.
Maegan Tucker, Noel Csomay-Shanklin, Wen-Loong Ma, and Aaron D Ames. Preference-based learning for user-guided hzd gait generation bipedal walking robots. In 2021 IEEE International Conference Robotics and Automation (ICRA), pp. 2804 2810. IEEE, 2021.
Handing Wang, Markus Olhofer, and Yaochu Jin. A mini-review on preference modeling and articulation in multi-objective optimization: Current status and challenges. Complex & Intelligent Systems, 3:233 245, 2017.
Christian Wirth, Riad Akrour, Gerhard Neumann, Johannes Fürnkranz, et al. A survey of preference-based reinforcement learning methods. Journal of Machine Learning Research, 18(13)):1-46, 2017.
H Peyton Young. A note on preference aggregation. Economelrica: Journal of the Econometric Sociely, pp- 1974.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5):1538-1555) 2012.
Yichi Zhang, Daniel W Apley, and Wei Chen. Bayesian optimization for materials design with mixed quantitative and qualitative variables. Scientific reports, 10(1):4924, 2020.
Zhanhui Zhou, Jie Liu, Chao Yang, Jing Shao, Yu Liu, Xiangyu Yue, Wanli Ouyang, and Yu Qiao. Beyond one-preference-for-lll Multi-objective direct preference optimization. arXiv preprint arXiv:2310.0370 2023.
Eckart Zitzler, Lothar Thiele, Marco Laumanns, Carlos M Fonsoca, and Viviane Gruncrt Da Fonscca. Performance asscssment of multiobjective optimizers: An analysis and review. IEEE Tronsactions on Evolutionary Compulation, 7(2):117-132, 2003.
13

---

Published in Transactions on Machine Learning Research (05/2025)
A Proofs of theoretical results
A.1 Notation and auxiliary results
We first introduce the following notation. Let Fa denote the o-algebra generated by Dn-1 and Foo denote the minimal o-algebra generated by (Fn)== We denote the conditions probability measures induced by Fn and Fsx by P. and c.. respectively. Unless otherwise stated, throughout this analysis, we assume that f is a random function drawn from the prior.
We will now prove two lemmas. Lemma D guarantees that for any Pareto optimal point, there is set of scalarizations with positive measure for which this point is optimal. Lemma 2 the other hand, ensures that promising points are compared against the reference point sufficiently many times.
Lemma 1. Let f be any fized function. If x E x then there erists v θ such that is the only element of argmax s(f(x'); 1) for all vp and P(O V O, where 0 is uniform random variable over θ
Proof. From Theorem 3.4.6 in Miettinen 1999), know that E X ( (i.e. x is properly Pareto optimal) if and only if there exists 0 @ such that the only element of argmax ((ffxxxxxxx((((()))))))) ()) As result, since x E x,, there cxists at least one I E θ such that x is the unique maximizer of s(f Since X is finite, the function s(f(2'); is continuous with respect to 0 and is the unique maximizer at 6, by continuity, there exists a neighborhood around 0 where x remains the unique maximizer. Tet T be this neighborhood around 0. Since is uniformly distributed over θ the set V, being non-empty, has positive measure. Hence P(0E E ) > O.
Lemma 2. Suppose that the assumptions of Theorem hold and let x E X be any point with Po E x7) > O. Then, [xx - (Evet) is Fox -measurbuee for j l.... m.
Proof. Making a slight abuse of notation, we write x = argmax 8 ((((2):)) if a is the only element of argmax,rex ()
Let denote a uniform random variable over θ independent of Foc. The existence of such a guaranteod by Kolmogorov's extension theorem.
From Lemma there exists a V C @ (depending on f) such that (oo argmax ( and P Poo(t ( E > O.
A standard Martingale argument shows that
lim (n
P argmax a V v) a'eX
xexx
almost surely.
This convergence to a positive limit implies that for sufficiently large n, the conditional probability is bounded below by some 6 > such that (n argmax s(f(x'); ): v) that (0 e v) > eg for all n large enough.
E v > c₁. Similarly, we can find 62 such
Under the modified DSTS policy where the F,, defaults to Fzef with probability 8, we have
(x (x, xrot)) 2 Pa(x argmax
sf(('))))))))))))) v V e V.P, 4) > e1e2ō
z'ex
for all n large enough. It follows that the event X, = (I, Trert occurs for infinitely many Let n2, 72,... denote the sequence of indices such that X = (I, Iret). Since q = 2,
E(ry,mz 1 [ = P( =
exp( (Iret)/)g)
exp(fs(x)/2n) (xp((((Fret)/2))
14

---

Published in Transactions on Machine Learning Research (05/2025)
Thus, by the law of large numbers we have
exp(ff(Fret) (rema -1 (xp(f)(=)/))) + exp(f,(2ret)/))
lim K-400
K
kml
+ exp(((j((r) (xrrtt))
almost surely. We deduce from this that fz(2) - fyl (arot) is F Fs--masurrble for j = 1,..., m.
A.2 Proof of Theorem 1
Theorem 1. Suppose that X is finite, 1, and the sequence of queries {xn) is chosen according to the DTS policy. Then, for each x E X, lim,-toe (n e argmax f(x') = 1(x x argmax f(x)) almost sureky for f drawn from the prior.
Proof. Observe that X; argmax f(x') in the single-objective setting. We will show that the event << Pxox E X;) occurs with probability zero by showing that a contradiction arises almost surely.
Since (x E x < 1, there must exist a fixed a' E X such that (f( > f(x)) > Moreover, we can choose such that Poo (a' E x > O. Similar to the proof of Lemma 2 this implics that we can find En 0 such that (n xj) > en and P., E xX))) > ex for all large enough.
Now observe that under the DTS policy,
(x (x, x' ..... r')) (n E x (x' E ex)) C
for all large enough (note that have used that In,1:-.., Fngg are chosen independently). This implies that the event Xn (z, ,'..,,,'') 2') occurs infinitely often almost surely. Similar to the proof of Lemma this implics that
exp(f(x)/A) exp(f(x)/A) + -1
and
exp(f(z')/A)
exp()(=)/A) (4- exp(
are both Foo -e-eaurrable By taking the ratio between these two quantities, we see that exp((f(x)- f(x))) is mee-suaure,le,, which in turn implics that f(x) f(x') is also Fes-maauurabl.. From this, it follows that (fx(((z)) f(x)) 1{f(x') > f(x)).
Now recall that (f > f())) 0. Thus, must be the case that (oo((())) f(x)) However, this implies that P= E X7) 0, which is contradiction.
From the above, it follows that Po (xr E X2) is 0 or almost surely. Similar to the proof of Theorem conclude that P (I E Xj) = 1( E X3} by virtue of Doob's Bayesian consistency theorem (Doob] 1949
7
A.3 Proof of Theorem 2
Theorem 2. Suppose that X is finite, q 2, and the sequence of queries 1x is chosen according to the modified DSTS policy. Then, for each x E X, lim Pn(x E Xj) = 1(x r Xj} almost surely for drawn from the prior.
Proof. A standard martingale argument shows that lim (a EXi) = P (a E X3) almost surely. Thus, it remains to show that (x E X2) 1xx E X;} almost surely.
To prove this, we will show that the event 0 P (x E X7) < 1 occurs with probability zero. For the sake of contradiction, assume this event holds with positive probability. As we will see next, this yields a contradiction that holds almost surely.
15

---

Published in Transactions on Machine Learning Research (05/2025)
Since (x E x3) < 1, there must exist x' E X such that Po x x) > 0. Moreover, can choose x' such that P (x Exx) > 0.
Given (r E X7) > 0, fz(x) - fz((rot) is Feemeaaurbele for each j = 1,..., m by Lemma Similarly, since P (x E xxy) > 0, ff(²) - ff((zet) is F measurable. Thus,
(f((²) (y((ret)) - (Jz(z) fz((roo)) [5(2) - fz(()
is Tee-urraee for each j ,,...,77
Next, observe that r' f if and only if miny=1...... 11())-15) > O. Hence, 1fx6 by x} is -me-surrbbll and (x 1 x) = 1aa 5 2} almost surely.
Recall that Poo (x' os x) > O. Thus, must the case that Poo (x' > x) = 1. This implies that ( E x7) O, which contradicts our initial assumption that 0 Pxo E x7) <
Finally, since Po (xr xx)) is 0 1 almost surely, from Doob's Bayesian consistency theorem DDob 1949) conclude that P (x E xj) 1/x E X
A.4 Proof of Theorem 3
Theorem 3. There exists problem instance with finit X and 2 such that if Xn e argmax xex: (EHVI, for all n, then lim Pu(x E Xj) I almost surely for some flaed E X and t E 1),
Proof. For simplicity, we focus on the single-obeective case. Our example can be easily extended to the multi-objective case, e.g., by augmenting the problem with dummy constant objectives. In this case, ; = argmax,"'xx f(x') and the qEHVl acquisition function reduces to the qEI acquisition function (Sivola et al. 2021). defined by
(I), Ex((s(=)- 1+,)+,
(4)
where nn is the maximum posterior mean value over designs previously shown.
We build on the example provided by Astudillo et al (0023) Specifically, let X (1, 4) and consider the functions f( ;k) X R, for k 1,2, given by f(1:k) -1 and f(2; k) 0 for all k and
L, ==3
2 x=3
1(x:1)
f(x;2)
1 4
1,
x=4²
1 ==3
-1,
x=3
f(x;3)
f(x;
-1,
x
4=4
2
I 4=4"
Let be number with 1/3 and set = -1-8, We consider prior distribution on f with support
[f( [1)) such that
s//,, k 1,1,
Pf ;k) P0, = P
1/2,, k == 3.
We assume a logistic likelihood given by
exp(f(xn.s)/A) P (r,, = i i(X,)) = exp(f(xn,1)/A) + exp (f i= 1,2.
From the proof of Astudillo et al.
2023 we know that X, = (3, 4) for all n and the posterior distribution
evolves according to the equations
PoikWng h = 1,
Pot1.
P1, - wa). = 2,
16

---

Published in Transactions on Machine Learning Research (05/2025)
where w,, al = + (1-r),fr, 2} and exp(1/2X).
We will use the above to show that Pn.3 + Pn, = for all n. To this end, observe that the above equations imply that Pn.1/Pn.3 = Po.1/Po.3 = s/t for all n. Similarly, Pa.//nnd P0.2/Po.4 = s/t for all n. Thus, Pn.1 = (s/t)pn,3 and pn, = (8/t)pn,4 for all n. Moreover,
Pn,1 + Pn.2 + Pn.3 + Pn.4 (s/t)pn,3 + (s/t)pn,a + Pn, Pn.
(Pn,3 p1, + 8/t).
Therefore,
Pn.3 Pn,4 = 1/(11 s/t)
t.
Finally, let x = 2 and observe that E argmax, fx²) if and only if f- f( :3)) or f = f( :4). Hence,
Pn
x E argmaxx s(xd))
= Pa - (3:3) or f (4)
n'EX
Pn, + Pn,4
t.
B Additional experimental details and results
B.1 Additional details on our probabilistic model under observable objectives
Suppose for concreteness that objective j is observable. Then, at cach itcration n, we observe (potentially noisy) measurements of (f(,,,)), ( Let yo.1.---> Un..q denote these measurements, and let. Dz-1 denote all the measurements available right before the n-th interaction with the DM. As is standard in the BO litcrature, we can assume Gaussian noise such tat Yr, fy (xn,s) + Gu,i where the terms Cn,i N(0, o²) are independent across n and i. If we assume a Gaussian prior over fj, then the posterior distribution of ʃJ given D again a Gaussian process, whose mean and covariance functions can be computed using the standard Gaussian process regression equations (equations 2.23 and 2.24 of Rasmussen & Williams, 2006
( (..)),=1....,.=11
B.2 Noise in the DM's responses
In our experiments, we simulate noise the DM's responses using additive Gumbel noise. Specifically, if X is the query presented iteration n, then the response observed is т, . mm, where
Tjn argmax (In,s) + en,igf
i=1....
and Enjij Gumbel(O, Atrue) for i 1, 1,...,g and j 1, 1,..., are independent. Under this choice, we have exp(f)(2n..)
P Prrm==il =ilf((X)))) DI= exp(S (5 )/ )/2rr0))
for i .......... q, i.e, this recovers a Logistic likelihood.
Following Astudillo et al. (0023). in each problem, for every objective, Atme is chosen such that, on average, the DM makes mistake 20% of the time when comparing pairs of designs among those with the top 1% objective values within X. We estimate this percentage by uniformly sampling a large number of design points over x.
17

---

Published in Transactions on Machine Learning Research (05/2025)
Noise in the DM's responses observed by PBO-DTS-IF is generated by scalarizing the corrupted objective values defined above using Chebyshev scalarization. Concretely, if r, denotes the response observed by PBO-DTS-II when presented with query X2. then
argmax s (f + en,ii 0n),
where 6n (enii,l .... mngimb) En,i. is defined as before, and 0, is drawn uniformly from θ.
0.08
350
0.06
hypervolume
hypervolume
hypervolume
300
0.04
250
0.02
DSTS-M
0.00
50
100
50
100
0
50
100
number of queries
number of queries
number of queries
(a) Car Side Impact
(b) Autonomous Driving
(c) Exoskeleton
Figure 6: Performance of DSTS and modified DSTS (DSTS-M) using queries with 2 alternatives across three test problems. Their performance almost identical the three problems considered.
B.3 Results for modified DSTS
We evaluate the performance of the modified version of DSTS used in the proof of Theorem on three of our test problems. We set Øzef by drawing a point uniformly at random over X. This point is different for each replication. In addition, we set d 0.05 such that Fref is selected five times on average across 100 iterations. The results shown in Figure
B.4 Results for y 4
We carry out experiments analogous those presented in the main paper, using queries with q alternatives each. We focus DSTS and the two strongest benchmarks, qParEGO and qMES. The results shown in Figure 7 For clearer comparison, alternatives improves the performance of the three algorithms. DSTS delivers the best overall performance under queries with q = 2 and 4 alternatives.
also include results for q 2. As depicted, increasing the number of
B.5
Additional details on our benchmarks
B.5.1 Adapted standard multi-objective BO algorithms
qParEGO In standard multi-objective BO with observable objectives, the qParEGO acquisition function is defined by (x) E,, [=([((((()))))) max ((f(x')00))) where X, the set of all designs in queries presented to the DM up time and on is drawn uniformly at random over e. Following SSivola et al. (2011), we replace f(x') by the posterior mean of f at x' to avoid taking the expectation with respect to the random variable max (f(()))
qEHVI In the standard multi-objectivy BO setting with observable objectives, the qEHVI acquisition function defined by (x) = E, [H, U (f())),r) HV(),. r)], where Vn, the set of objective voctors corresponding to designs presented the DM up time n. As with qParEGO, we replace these objective vectors with posterior mean vectors to avoid taking the expectation with respect to these unknown values.
18

---

Published in Transactions on Machine Learning Research (05/2025)
160000
0.40
225
0.35
hypervolume
150000
hypervolume
hypervolume
200
0.30
140000
qMES, q-2
dPerEGO, 8=2
0.25
175
DSTS, q-2
qPerECO, Q=4
0.20
150
qMES, q-4
130000
0.15
125
0
100
0
50
100
0
50
100
number queries
number of queries
number of queries
(a) DTL.71
(b) DTT.72
(c) Vehicle Safety
0.08
400
0.06
hypervolume
350
hypervolume
hypervolume
0.04
300
0.02
250
0.00
50
100
50
100
0
50
100
number of queries
number of queries
number of queries
(d) Car Side Impact
(e) Autonomous Driving
Exoskeleton
Figure 7: Performance of qParEGO, qMES and DSTS using queries with = 2 and g == 4 alternatives across our six test problems. Using a larger number of alternatives improves the performance of the three algorithms. DSTS delivers the best overall performance under queries with q 2 and q = 4 alternatives.
Note that qEHVI also requires specifying reference point r, which is challenging if the objectives are latent. In our experiments, we set equal to the coordinato-wise minimum posterior mean value across designs presented to the DM up to time n.
Unlike qParEGO and qEHVI, qMES does not require any modification to be applicd in our setting. However, it worth noting that. the lookahead step the definition of qMES assumes that the objective values will be observed at the selected points. However, this not the case in our setting. We believe this be problematic as it may cause qMES to over-value queries constituted by designs with very distinct. objective values, even though preference feedback from such queries can often be uninformative.
qMES
B.5.2 PBO with inconsistent preference feedback
The foedback used by PRO-DTS-IF is produced as follows. At cach itcration n, a set of scalarization parameters On, is drawn uniformly random over O. Given query X, = (In, Fngg) we assume the DM then provides a noisy response to argmax;=1,... (zn.)))) Inconsistency arises from sampling different scalarization parameters at every iteration, which, in general, implics that preferences cannot be encoded by a single objective function. We argue this mimics the DM's desire to explore the trade-off between objectives before committing to a solution. At the same time, we note that these responses respect intuitive user behavior, such as preference for queries for which each objective is as large as possible.
The responses provided by the DM are used to fit a (singlo-output) Gaussian process with a Logistic likelihood for which posterior inference is carried out using the same approach we use for the other algorithms. New
19

---

Published in Transactions on Machine Learning Research (05/2025)
queries generated using the (single-objective dueling Thompson sampling strategy under this probabilistic model. The performance of this method is expected to be poor when the Pareto-optimal set is large, i.e., when the trade-ofis between objectives are significant.
Problem/Algorithm
PBO-DTS-IF
qParEGO
QEHVI
qMES
DSTS
DTLZ1
5.7
24.3
25.6
58.5
19.2
DTLZ2
6.8
16.4
10.6
16.5
13.3
Vehicle Safety
8.4
15.4
36.7
43.8
17.8
Car Side Impact
5.9
38.1
352.8
324.4
36.3
Autonomous Driving
5.5
34.1
102.7
72.2
32.1
Exoskeleton
6.3
16.5
23.7
59.3
14.6
Table 1: Average runtimes in seconds for all the algorithms compared (except for Random) accross all test problems.
B.6 Runtimes
The average runtimes for all algorithms across all test problems are presented in Table I DSTS is comparable with qParEGO and faster than qEHVV and qMFS. PBO-DTS-IF is the faster algorithm since, in contrast. with the other algorithms, it requires single Gaussian process model instead of However, it is worth noting that the runtimes of these algorithms could be reduced by parallelizing the training step of its m models. Moreover, the runtimes of DSTS could be further reduced by parallelizing the generation of the alternatives each query during the optimization step.
20


Reviews:
[{"review_id": "UGp6hQZq2F", "reviewer": "Reviewer_Pwf1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The paper shows convincing empirical results that the new algorithm performs well on this new class of problems.\n2. The writing is generally clear and informative.\n\n\nWeaknesses\n1. I somewhat feel that the problem setting is a bit contrived and would like to see more motivation for it. Do we really have a situation where a DM or a set of DMs are giving preference feedback on individual outcomes? Couldn't we ask them to give preference feedback on multiple outcomes (see next comment) instead? That seems simpler.\n2. PBO has previously been viewed in past work as helping to address a “multi-objective”-like situation (see, e.g., [1], where the authors discuss this in the introduction), where the preference function is over a multi-dimensional outcome space (using the language of Figure 1, this would be (f1, f2)). The idea in [1] is that when one is in a multi-objective setting, there always exists some latent utility over the Pareto front, and PBO can be more efficient in exploring the Pareto front because it explicitly tries to learn this utility function.\nIn the current paper, there is one sentence dedicated to this. I wonder if the authors could do a better comparison here?\n2. Related to the above comment: in this work, once the Pareto frontier has been found, what happens next? I would be curious to understand this point, especially in the context of the applications given here. For these applications, it seems like there must then be a “final decision maker” who selects a point from the Pareto frontier? Would that decision maker put us back into the framework of [1]?\n3. I think the qEUBO paper [2] is not discussed in the Related Work. I think it should be added and compared.\n4. “assuming independent pairs of arms. This result does not apply to our setting, where arms are may be correlated” -- can the authors clarify this point? Suppose in the new setting we had independent Gaussian priors on each arm. Could we then prove the convergence rate result in Thm 2 of [3]?\n5. Figure 5 is very interesting. However, I’m not sure saying the qParEGO is worse than DSTS because of the region near y2=0 is convincing since DSTS also doesn’t explore that area fully + DSTS seems to have more non-Pareto points. Further, DSTS doesn’t explore the area y1=0 very well compared to qParEGO.\n6. I find the qEHVI result interesting. Perhaps that could be moved to the main paper with some intuition.\n\n[1] https://proceedings.mlr.press/v151/jerry-lin22a/jerry-lin22a.pdf\n\n[2] https://proceedings.mlr.press/v206/astudillo23a.html\n\n[3] https://arxiv.org/pdf/1705.00253", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a framework for Preferential Bayesian Optimization (PBO) in a multi-objective setting. The authors introduce Dueling Scalarized Thompson Sampling (DSTS), an extension of Dueling Thompson Sampling (DTS) to the multi-objective case. The method is evaluated on synthetic test functions and two real-world inspired applications (exoskeleton personalization and autonomous driving policy design). The authors prove the asymptotic consistency of DSTS.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses section.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UpyUaK2nCc", "reviewer": "Reviewer_pJ9s", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The paper considers a new understudied problem of multiple objective black-box optimization with preference evaluations. \n\n- The proposed approach is simple and works well on synthetic and simulation benchmarks. \n\n- The theoretical analysis is sound. It would be good to clarify the new aspect in the theory (which seems to be Lemma 2) for the readers.\n\n- The paper is very well written and easy to understand. \n\nQuestions\n\n- Since it is assumed that the same decision maker provides preferences for multiple objectives, there is a higher chance for the objectives to be correlated. Please discuss or analyze the choice of using independent GPs for modeling the objectives versus using a multi-output/multi-task GP. \n\n-  Since the evaluation metric in the experiments section is based on hypervolume, it might be useful to consider scalarization techniques that are directly to hypervolume improvement. Please see [1] for reference.\n\n- It does seem a bit counterintuitive that larger batch size leads to faster convergence in Figure 7. \n\n- The analysis of DTLZ2 where the proposed method doesn't perform better than the baselines is nice. However, there is limited description of why does the method performs well on other benchmarks where it outperforms other baselines. \n\n- It is surprising that qMES is consistently better than qEHVI in all the benchmarks since EI acquisition functions tend to show better practical performance (even in single objective preference optimization [2]).\n\n- I appreciate the two applications (exoskeleton task and autonomous driving policy design) mentioned in the paper but providing preferences for multiple objectives might also increase the cognitive burden for the decision maker. Single objective preference queries are preferred over scalar rewards primarily because of decrease in cognitive burden but I am not sure if this advantage remains with multiple objectives. \n\n\n[1] Zhang, R., & Golovin, D. (2020, November). Random hypervolume scalarizations for provable multi-objective black box optimization. In International conference on machine learning (pp. 11096-11105). PMLR.\n[2] Raul Astudillo, Zhiyuan Jerry Lin, Eytan Bakshy, and Peter Frazier. qEUBO: A decision-theoretic acquisition\nfunction for preferential Bayesian optimization. In International Conference on Artificial Intelligence and\nStatistics, pp. 1093–1114. PMLR, 2023.\n\n\nOverall, I think the paper studies a new problem and presents a simple approach that works well. I am happy to recommend acceptance for this paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the problem of multi-objective black-box optimization where each objective can be evaluated with a preference feedback. In order to address this problem, the paper introduces a method for extending preferential Bayesian optimization (PBO) to problems with multiple latent objectives. The key idea is to model each latent objective with an independent Gaussian process and leverage Chebyshev scalarization to map the multi-objective problem into a single-objective problem. At each iteration, the algorithm (named DSTS i.e. dueling scalarized Thompson sampling) draws independent posterior samples of the objectives, applies a random scalarization, and then selects a batch of designs. It is shown theoretically that a modified version of DSTS is asymptotically consistent in the multi-objective setting. Empirically, the method is evaluated on six test problems—including four synthetic benchmarks and two simulated tasks in exoskeleton gait customization and autonomous driving policy design. The experiments suggest that DSTS outperforms several adapted baselines (such as qParEGO, qMES, qEHVI) in terms of exploring the Pareto front, as measured by the hypervolume indicator.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see strengths and weaknesses section.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cwEbVyRJcp", "reviewer": "Reviewer_Ja3w", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. This paper proposes preferential multi-objective Bayesian optimization.\nTo the best of my knowledge, this setting has not been studied before, and seems to be useful in practice.\nHence, it is interesting to investigate this setting.\n\n1. The sampling policy proposed in this paper (dueling scalarized Thompson sampling) is quite standard.\nIt is essentially Thompson sampling of the scalarized objectives, which is exactly the same as Praria et al. (2020).\nIn addition, this Thompson sampling policy has been used as a baseline in previous multi-objective BO papers (e.g., Daulton et al., 2020)\nThus, I do not think the sampling policy itself is a contribution of this paper.\nInstead, the message from this paper is that Thompson sampling outperforms other multi-objective acquisition functions like qEHVI, qMES, and qParEGO in preferential multi-objective BO.\nThose baselines were not initially designed for preferential BO, though.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a new Bayesian optimization setting where the goal is to maximizing multiple latent objectives using preference observations.\n\nThe authors propose an acquisition function called dueling scalarized Thompson sampling, which performs Thompson sampling on a scalarized objective based on an augmented Chebyshev scalarization.\nThey prove the asymptotic consistency of the proposed sampling policy under two conditions: (a) the batch size is fixed at \\(q = 2\\) and (b) the policy is modified so that, with a constant probability, one of the queries is a fixed reference point.\n\nExperiments on six benchmark problems demonstrate that the proposed sampling policy outperforms baselines in most cases.\nSince this paper explores a new setting, the baselines are primarily acquisition functions for non-preferential multi-objective Bayesian optimization, adapted to the new setting.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. In Section 4.3, the assumptions and conditions need be clearly stated.\nWithout these, it is unclear how to interpret and verify the statement.\nSpecifically, it is unclear what is the exact assumption on \\\\(f\\\\).\nBy skimming through the appendix, it seems that \\\\(f\\\\) is an unknown *fixed* function and the probability \\\\(\\Pr_n(x \\in \\mathbb{X} _ f^\\*)\\\\) is only over the stochasticity of Thompson sampling.\nHowever, it is well-known that GPs cannot fit all functions.\n\n1. Make baseline details more clear.\nSince most baselines are acquisition functions for non-preferential BO adapted to preference observations, it is crucial to include these details in the main paper.\nAs TMLR is a journal without page limit, it is better to move their descriptions to the main paper.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This manuscript concerns multi-objective Bayesian optimization in a preferential setting, where observations take the form of preferences over pairs (or more) of points in the design space rather than direct measurements of the objective functions. To this end, the authors propose a dueling algorithm based on scalarized Thompson sampling. This algorithm appears to work well in practice in an empirical study, and the authors also provide some theoretical consistency results.

Overall, the reviewers received this work well during the initial review phase, noting that the manuscript was well-written and that the ideas presented were well motivated and defended. The reviewers did ask a series of questions and raise a series of comments, which were addressed satisfactorily by the authors during the discussion phase.

Ultimately the three reviewers were unanimous in their recommendation to accept the paper to TMLR, a decision I also support.
Decision: Accept (poster)