When a new user arrives at a system that must balance conflicting goals, such as a route planner trading distance against fuel and familiarity, or an exoskeleton trading comfort against battery life, the hard part is usually not computing the best trade-offs. Those can often be precomputed as a Pareto front: the set of solutions where no goal can improve without another getting worse. The hard part is finding out which point on that front this particular person wants, while asking as few questions as possible. We propose to ask the newcomer pairwise questions ("A or B?") chosen to maximize information about one quantity only: which front solution they would pick. Their likely answer is predicted from a prior learned from earlier users, and that prior groups earlier users into an unknown number of trade-off "archetypes."
The point is that three things interact. First, the questions aim at the decision rather than at the whole utility function. Second, the population is modeled as a mixture whose number of components is inferred, not fixed. Third, the earlier users' own data is sparse and noisy. When each earlier user answered only a handful of comparisons, a clustering model can pool them into sharp archetypes. A simple average or smoothed estimate of their noisy weight vectors cannot. Sharp archetypes are what let a few well-chosen questions settle a newcomer's choice quickly. The mixture also keeps some probability on "none of the known types," so a newcomer who matches no archetype is noticed rather than forced into the nearest one.
Core Claim
Our hypothesis is that, for cold-start multi-objective personalization, this combination needs fewer questions to reach low regret than each of the following: a single global population prior, an unsmoothed empirical prior built from earlier users, and single-user preference optimization. The combination is decision-targeted mutual-information acquisition under a Dirichlet-process mixture prior over trade-off weights. We expect the advantage over an empirical prior to grow as the earlier users' data gets sparser. We also expect a clear advantage for newcomers from archetypes absent from the training population.
Concretely, let $\mathcal{X} = \{x_1,\dots,x_N\}$ be a precomputed pool of Pareto-optimal solutions with objective vectors $f(x_n) \in \mathbb{R}^K$. Each user $u$ has weights $w_u$ on the probability simplex. Their utility is an augmented Chebyshev scalarization $U_{w}(x) = -\max_k w_k |f_k(x) - z_k| - \rho \sum_k w_k |f_k(x)-z_k|$, where $z$ is a reference point and $\rho$ a small constant. We use this form because, unlike a weighted sum, it can make any point on a non-convex front optimal. The user's chosen solution is $x^\star_u = \arg\max_{x\in\mathcal{X}} U_{w_u}(x)$. Answers to a query $(a,b)$ follow a logistic choice model in $U_{w_u}(a) - U_{w_u}(b)$. After the newcomer's answers so far, $D_u$, the next query maximizes
$$\alpha(a,b) = H\big[y_{ab}\mid D_u\big] - \mathbb{E}_{x^\star_u \mid D_u}\, H\big[y_{ab}\mid x^\star_u, D_u\big],$$
where $y_{ab}$ is the binary answer and $H$ denotes entropy. Because $x^\star_u$ takes only $N$ discrete values, both terms can be estimated exactly from weighted posterior particles over $w_u$. No Monte Carlo sampling of fronts is needed, and the cost per query is milliseconds.
Relation to Prior Work
The closest single-user method is Preferential Multi-Objective Bayesian Optimization. It learns a Pareto front from pairwise comparisons using Dueling Scalarized Thompson Sampling and shows that naive hypervolume-based acquisition (qEHVI) gets trapped and does worse than random. That result constrains our design: we do not adapt hypervolume criteria to preference data. DSTS uses no population information and no information-theoretic acquisition, and those are the two things we add.
The information-theoretic machinery for fronts comes from MESMO and MF-JESMOC. Both maximize information about the whole front or Pareto set from direct numerical evaluations. Our target is narrower and cheaper: one user's selected point on a front that is already known.
Two papers motivate the population side. Gaussian Process Preference Elicitation borrows strength across users through one global Kronecker-structured covariance and picks queries by expected value of information. It reached in 4–6 queries an accuracy that other methods needed 10+ queries to reach on Sushi. CAPE learns population correlations offline and then runs training-free Bayesian linear regression online with information gain. It reports 80.8% alignment on PrefDisco against 68.5% for reinforcement learning. Both methods assume a single unimodal population and a scalar objective. We replace their global prior with a mixture of unknown size over trade-off weights.
That mixture idea is supplied by DPM3, which recovered the true three clusters on pref30 in 93% of runs versus 57% for finite mixtures, but only offline and only for single-criterion rankings. A second source is RAMBO, which places a Dirichlet-process mixture of GPs inside single-objective optimization. RAMBO's online collapsed Gibbs sampling is too slow for real-time questioning, and that constrains our design: all mixture inference over the population happens offline.
Research Program
The method has an offline stage and an online stage.
Offline stage. We fit a Dirichlet-process mixture over the simplex to the earlier users' pairwise choice data. Each component is a Dirichlet distribution over $w$, and the likelihood is the logistic Chebyshev choice model above. Inference uses Metropolis-within-Gibbs with data augmentation in the style of DPM3, with the concentration parameter given a prior rather than fixed. This targets the fragmentation-versus-oversmoothing failure noted for fixed concentration parameters.
Online stage. The newcomer's prior is the posterior predictive of the mixture: a weighted set of fitted components plus the base measure, with the base measure's weight set by the concentration parameter and population size. The mixture's state is averaged over several posterior samples. Label switching does not matter here, because only the predictive distribution is used. We represent the newcomer's belief over $w_u$ with a few thousand importance-weighted particles drawn from that predictive. Particles are reweighted after each answer and rejuvenated with a short Metropolis step. Queries are chosen by $\alpha$ over pairs from the pool. Following the combinatorial elicitation work, we restrict candidate pairs to a diverse subset for speed. We stop when the posterior mass on the modal $x^\star_u$ exceeds a threshold, so the number of questions adapts to how quickly this user's choice is settled.
Analysis. We will study two things. The first is how pooling within clusters sharpens archetypes as a function of the number of comparisons per earlier user. The second is how the base-measure weight trades false novelty alarms against detecting genuinely new types.
Baselines
The do-nothing reference recommends, without asking anything, the front point most often chosen by earlier users. It is a population-mode recommendation. Random pairwise queries with the full mixture posterior serve as a second floor; this separates the value of the prior from the value of the acquisition rule.
The strongest existing population method is a CAPE-style elicitor following CAPE. It uses a single Gaussian prior on weights, fit to the same earlier-user data, with information-gain query selection. On PrefDisco, the reported number to beat is 80.8% alignment. We add a GPPE-style variant with a single global user-feature kernel and expected value of information (GPPE). No exact loss values are reported for it on Sushi in the material available to us.
The strongest single-user method is DSTS (Preferential Multi-Objective Bayesian Optimization), given the same front pool and the same question budget. No reported hypervolume or regret number for it was found on Lacuna.
On PC-TSP, the pool-based UCB elicitor with Bradley-Terry estimation (Preference Elicitation for Multi-objective Combinatorial Optimization) is the reference. It reports reaching under 10% regret with about half the queries of the ChoicePerc baseline, and satisfying the simulated decision-maker in 100% of cases versus 75%.
We also run four ablations that isolate the key ingredients. The first keeps the mixture prior but replaces decision-targeted information with information about $w_u$ itself. The second keeps the acquisition rule but uses a finite mixture with $k$ chosen by BIC. The third uses an empirical prior made of the earlier users' point estimates of $w$, smoothed by a kernel. The fourth replaces the Chebyshev utility with a linear one.
All methods share the same earlier-user data, front pool, choice-noise model, and question budget. Each tuned hyperparameter, such as kernel bandwidth, $k$ range, or prior scales, gets the same 20-configuration search on a validation split of users. Our method counts as better only if its regret curve lies below a baseline's with non-overlapping 95% bootstrap intervals over newcomers at budgets of 3, 5 and 10 questions.
Why not just…?
Why not just ask for weights directly, or use a weighted sum with expected improvement? People have trouble stating numeric weights. A weighted sum also cannot make points on non-convex parts of a front optimal (Cheng et al.; Zhang). The linear-utility ablation on DTLZ2 and PC-TSP, which include non-convex regions, measures how much regret this costs. We expect the gap to vanish on convex fronts, and we will report it either way.
Why not just use the earlier users' estimated weights as a smoothed empirical prior, with no clusters at all? This is the real threat. When earlier users have rich data, a smoothed empirical prior closely approximates the mixture's predictive distribution, and it may match our method. We claim an advantage in only two regimes. One is when earlier users have few comparisons each, because their individual estimates are then blurred and pooling within clusters undoes the blur. The other is a newcomer from an unseen archetype, to whom an empirical prior gives near-zero probability. The sparsity sweep and the held-out-archetype test below settle this. If the gap is negligible at realistic sparsity, we will report that the contribution is decision-targeted acquisition with a population prior, and that cluster cardinality does not matter.
Why not just fix $k$ with a finite mixture? DPM3 found that finite mixtures recover the true count in 57% of runs versus 93% for the nonparametric model (DPM3). But cold-start regret, not cluster recovery, is what matters here. A BIC-selected finite mixture may be nearly as good for prediction, and DPM3 itself reports comparable predictive accuracy on MovieLens. The finite-mixture ablation measures exactly this. The likeliest place for a difference is novelty handling, since a finite mixture has no mass reserved for new types.
Why not just train a reinforcement-learning questioner? CAPE reports that reinforcement learning stays at 68.5% alignment, needs 3 to 5 times more interactions, and on AIME asks the same questions regardless of the answers (CAPE). We therefore do not rerun this baseline beyond citing it on PrefDisco.
Proposed Experiments
Synthetic tests. These are the primary tests, because ground-truth archetypes are known. We use the DTLZ2 front (2 and 3 objectives) and PC-TSP instances with 10–100 nodes over distance, duration, fuel and familiarity, following the combinatorial elicitation work. On each, we generate populations from 1 to 8 Dirichlet archetypes of varying separation. Each earlier user contributes $m \in \{2, 5, 10, 30\}$ noisy comparisons. Newcomers are drawn from held-in archetypes, and in a separate condition from an archetype withheld from training. The metrics are:
- normalized utility regret of the recommended point after $t$ questions;
- questions needed to reach 10% regret;
- top-1 accuracy at identifying $x^\star_u$;
- latency per query, which must stay under 100 ms to be usable live;
- for withheld archetypes, the area under the curve for detecting novelty from the posterior mass on the base measure.
Decisive check. This is the interaction between sparsity and prior type. The predicted outcome is that the mixture's regret advantage over the smoothed empirical prior is largest at $m=2$ and shrinks toward zero by $m=30$. We also predict a large advantage on withheld archetypes at every $m$. If neither pattern appears, the clustering component is unnecessary.
Separate effect of the acquisition rule. A second check compares decision-targeted information against information about $w$ under the same prior. We expect decision-targeted queries to win most when many weight vectors lead to the same front point, which happens on discrete PC-TSP pools. We expect little difference on dense continuous fronts.
Real population structure. For this, we use the Sushi data: 5,000 users with demographic features, and preferences over items with 15-dimensional features. We treat two or three item-feature axes, such as price and oiliness, as objectives over a small front. We fit population mixtures from subsampled comparisons and simulate newcomers by holding out users whose full rankings define their true choice. GPPE serves as the population baseline. As a stretch test against CAPE's reported 80.8% alignment, we cast PrefDisco's per-user attribute preferences as competing response attributes and measure alignment under the same interaction budget. We treat this as an exploratory comparison, because the construction of objectives differs from CAPE's setup.
References
- Preferential Multi-Objective Bayesian Optimization
- Max-value Entropy Search for Multi-Objective Bayesian Optimization.
- Joint Entropy Search for Multi-objective Bayesian Optimization with Constraints and Multiple Fidelities
- Gaussian Process Preference Elicitation
- Cold-Start Personalization via Bayesian Adaptive Questioning
- Bayesian nonparametric Mallows model for clustering preference data
- Regime-Adaptive Bayesian Optimization via Dirichlet Process Mixtures of Gaussian Processes
- Preference Elicitation for Multi-objective Combinatorial Optimization with Active Learning and Maximum Likelihood Estimation
- Preference-Based Policy Iteration: Leveraging Preference Learning for Reinforcement Learning
- Optimal Scalarizations for Sublinear Hypervolume Regret