Batch Comparisons as Drift Detectors in Preferential Bayesian Optimization

Many design problems can only be judged by a person. Tuning a fire animation, a thermal comfort setting, or an exoskeleton's assistance profile works by showing the person several candidates and asking which one they like best. Preferential Bayesian optimization handles this well. It is a search method that keeps a probabilistic model of the person's hidden "utility" (how much they like each design) and picks the next candidates to show. Showing four options at once instead of two speeds it up considerably, as qEUBO demonstrates. These methods assume the person's taste stays fixed. In practice it does not. People get tired, notice trade-offs they had not considered, and form new wants once they see an option they had never imagined. When taste shifts, every old comparison keeps pulling the model toward the person's past self.

This note proposes a way to detect that shift using the batch query itself. When a person picks one of $q$ shown options, the model has already predicted how likely each pick was. A run of picks the model found unlikely is evidence that the person's taste has moved. We further propose spending one slot of each batch on a "sentinel" option, chosen to be the design on which the person's old and recent selves would disagree most. The extra slots that batching provides then also make drift visible. No drift rate has to be known in advance, and old data is never thrown out blindly.

Core Claim

Batch preferential optimization under drift has a structural advantage over single-point optimization with numeric feedback. Each $q$-way choice is a categorical observation with a full predictive distribution, and the person's surprise at that choice can be calibrated without assuming any drift model. We claim that combining three pieces lets batch preferential optimization track abrupt and newly triggered shifts in taste, without being told the drift rate, and with lower regret than discounting old data at a tuned rate. The three pieces are a choice-surprise change detector, a sentinel slot that sharpens the detector, and selective pruning of stale comparisons once the detector fires.

The detector works as follows. Let $\mathcal{D}_{b-1}$ be all comparisons before batch $b$, let $X_b$ be the $q$ shown designs, and let $k_b$ be the index the person picked. The surprise of batch $b$ is $s_b = -\log p(k_b \mid X_b, \mathcal{D}_{b-1})$. If the model is right, the expected surprise is the entropy $H_b$ of the predicted choice distribution. We accumulate a one-sided cumulative-sum statistic:

$$C_b = \max\left(0,\; C_{b-1} + \frac{s_b - H_b}{\sigma_b} - \kappa\right),$$

where $\sigma_b$ is the predictive standard deviation of $s_b$ and $\kappa$ is a small slack constant. The detector fires when $C_b$ exceeds a threshold $h$. The threshold is not set by hand or tied to a drift rate. It is calibrated by simulation: we draw utility functions from the current model, simulate the choices the person would make, and set $h$ to the quantile that gives a target false-alarm rate.

This idea adapts the trigger in Event-Triggered Time-Varying Bayesian Optimization, which fires when a numeric observation lies outside the model's confidence band. That trigger is undefined when no number is observed, and it is blind to changes in regions the search does not visit. The sentinel slot is our answer to that blindness.

Research Program

The base search method is qEUBO, which picks the batch maximizing the expected utility of its best option and is one-step Bayes optimal when choices are noise-free. We reuse it unchanged for $q-1$ slots.

The remaining slot holds the sentinel. Fit a second model only on the most recent window of comparisons. The sentinel is the design that maximizes the expected disagreement, measured by Kullback–Leibler divergence, between the choice distributions predicted by the full-history model and the recent-window model, given the other $q-1$ designs. This also resolves a tension the file identifies. qEUBO's theory relies on keeping a good incumbent in the batch, and under drift that incumbent goes stale. The sentinel is often exactly the old incumbent. Showing it is now useful twice over: it anchors the search, and it tests whether the person still likes it.

When the detector fires, we do not wipe the history. Dynamic Adaptation to Preference Drift in Interactive Evolutionary Multi-Objective Optimization reports that full wipes made its search erratic, while selective pruning improved final utility by 20% to over 70%. That result rules out the wipe-on-trigger design. Instead we borrow the backtracking idea from Brunzema et al. We refit on post-trigger data, then re-admit each older comparison whose outcome is not too improbable under the refit model, walking backward in time.

On the analysis side, we will characterize three properties. The first is detection delay as a function of the jump size in the person's utility and of the batch size $q$. We conjecture that delay shrinks roughly like $1/\log q$, because a $q$-way choice carries up to $\log q$ bits. The second is the false-alarm rate under no drift. The third is a dynamic simple-regret statement for piecewise-stationary utilities, in the spirit of the switching-environment bounds of DEX3.S, but over continuous spaces with Gaussian-process models.

Asynchronous evaluation by several people is a natural extension. As in Randomized Kriging Believer or asynchronous Thompson sampling, the system could keep proposing queries while earlier ones are still being judged. We treat that only as a stress test here, by delaying feedback, not as a core contribution.

Baselines

The naive reference is qEUBO with $q=4$ and no drift handling. It shows how much stale comparisons cost. Because it can only lose under drift, it serves as a floor.

The strongest competitor is qEUBO with exponential discounting of old comparisons in the likelihood. Each comparison is weighted by $\gamma^{T-t_i-1}$, following the Dynamic Bradley–Terry weighting of NS-DPO. In its offline language-model setting, NS-DPO kept reward accuracy above 60–70% after preference flips, while standard DPO fell to about 50–55%. That is the most direct evidence in the file that discounting works on preference data. We run it two ways. The first is a practical version with a single $\gamma$ chosen once on held-out drift scenarios. The second is an oracle version with $\gamma$ re-tuned per scenario. Our method must beat the practical version on average dynamic regret across drift regimes, and come within noise of the oracle, to count as a success. For qEUBO's own performance on these benchmarks, no reported result was found on Lacuna for numeric simple-regret values (the file reports only plots and relative orderings), so all baseline numbers will be produced in our own runs.

The third baseline is qEUBO with a Gaussian-process model whose kernel takes time as an extra input, with the time lengthscale learned by marginal likelihood. This is the textbook way to model smooth drift.

Two discrete baselines come next. One is periodic full restarts every $R$ batches, with $R$ tuned. The other is DEX3.S run on a grid discretization, included only for the 2- and 3-dimensional problems where a grid is feasible.

Two ablations isolate our ingredients. "Detector without sentinel" runs all $q$ slots under qEUBO and tests whether the sentinel matters. "Detector with wipe instead of pruning" tests the re-admission step.

Every method shares the same data generator, random seeds, query budget, Laplace-approximation preference model, and acquisition optimizer budget. Hyperparameters for every method get the same tuning budget, drawn from a separate set of drift scenarios.

Why not just…?

Why not just discount old comparisons at a fixed rate? This is the main threat, and the experiments are designed to settle it. Brunzema et al. report that fixed forgetting factors and periodic resets gave higher regret and variance than adaptive triggering on the Intel Berkeley temperature data. That finding, however, comes from numeric feedback. Preference data is noisier per query, so a moderate fixed $\gamma$ might be robust enough. We will sweep drift regimes from no drift, through slow drift, to abrupt switches. If a single held-out $\gamma$ matches our method across all of them, we will report that discounting suffices and that the contribution is confined to the sentinel's value for detection.

Why not just put time into the Gaussian-process kernel? For smooth, steady drift this may well be the best option, and we expect it to win there. Its weakness is abrupt or triggered change. A single learned time lengthscale must either forget fast all the time or adapt slowly to jumps. Learning that lengthscale from binary choices is also data-hungry. We scope our claim to abrupt and triggered shifts, and we will report the smooth-drift regime honestly even if the time kernel wins it.

Why not just discretize and run a non-stationary dueling bandit? DEX3.S has optimal dynamic regret, but its bound grows with the number of arms, and a grid has $m^d$ arms. The file also reports that bandit sparring needed thousands of iterations on the 2-dimensional Six-Hump Camel function. Preferential Bayesian Optimization reached near-optimal designs on the same problem in roughly 200 duels. We include DEX3.S at low dimension to confirm this gap under drift.

Proposed Experiments

The synthetic suite uses the latent utilities from the qEUBO and POP-BO papers: Ackley, Hartmann-6, Alpine1, and Branin. People's choices are simulated through a softmax over utility plus noise. Drift comes in three forms. Abrupt switches swap to a shifted and rotated copy of the function at unannounced times. Smooth drift moves the optimum continuously. Triggered changes add a new bump to the utility only after the search has shown a design inside a dormant region; this mimics the triggered preferences of AcCoRD, on which language agents scored as low as 0.09.

For realistic drift we use the Sushi preference data, switching the hidden utility between utilities fitted to different respondent groups mid-run. We also use DTLZ2 with drifting objective weights, following the drift model of the BCEMOA-HD paper, turned into a scalarized utility.

Metrics cover regret, detection, and cost. Regret is time-averaged dynamic simple regret, the current utility gap of the recommended design. Detection is measured by delay after each change and by false alarms per 100 batches under no drift. Cost is wall-clock time for acquisition, recorded across $q \in \{2, 4, 8\}$.

Three checks are decisive. First, under no drift, our method must match plain qEUBO, showing that calibrated thresholds rarely misfire. Second, under abrupt and triggered changes, it must beat the practical discounting baseline and the time kernel on dynamic regret. Third, removing the sentinel must measurably increase detection delay, especially for changes far from the current incumbent. If the third check fails, the batch is not doing the detection work we claim, and the method reduces to a choice-based port of Brunzema's trigger.