Theory: From Dueling Bandits to Kernelized Preference Optimization

How many comparisons does it take to find the best option, and does a comparison teach as much as a number? Chapter 21 introduced the theory of duels and its kernelized bounds; this chapter reports it in full, with each result's assumptions, and says where the proofs stop. Of the four layers of theory, finite-arm dueling bandits, linear and contextual dueling bandits, continuous convex dueling optimization, and kernelized preference bandits, only the last corresponds to preferential Bayesian optimization (PBO) itself, and its results came last.

The state of things as of September 2026, in three sentences. Kernelized upper bounds for a batched algorithm have reached the same order as order-optimal scalar Bayesian optimization, but no lower bound exists for any kernelized preference problem. The pipeline used in practice, the Laplace approximation with EUBO, has only one-step Bayes optimality and finite-domain consistency. And identification and aggregation theory shows that pairwise data are the weakest form of feedback when people differ or answers depend on hidden context.

29.1 Finite-arm and linear dueling bandits #

Before 2017. The finite-arm results of Section 21.2 anchor the theory: the Interleaved Filter's expected regret $O(K \log T / \Delta_{\min})$, matching its lower bound under strong stochastic transitivity and the stochastic triangle inequality (Yue et al., 2012), and RMED, which matches an asymptotic lower bound expressed through the Kullback-Leibler divergence between Bernoulli distributions (Section 6.2) (Komiyama et al., 2015). Dueling bandit gradient descent had expected regret of order $T^{3/4}$ on a continuous convex space (Yue and Joachims, 2009), and contextual dueling bandits introduced the von Neumann winner, a randomized choice over options that beats any single option with probability at least one half (Dudík et al., 2015).

2017 and after. The paper of González et al. (González et al., 2017) has no regret or convergence theorem (Section 26.2). SelfSparring (Sui et al., 2017b) assumes "approximate linearity", that the winning probability is a function of the utility difference that is approximately linear, which the authors call a stricter requirement than strong stochastic transitivity. Their Theorem 1 proves that the independent-arm version converges to the best arm, and their Theorem 2 gives an asymptotically optimal no-regret rate of $O(K \ln(T)/\Delta)$; an analysis of kernelized multi-dueling is missing, and a 2018 survey's statement that a Gaussian process prior reduces the sample complexity from $O(K)$ to $O(d)$ (Sui et al., 2018a) is a conjecture (Section 21.4.2). Winner Stays (Chen and Frazier, 2017) has weak regret, which counts a round as free if either option shown is the best, of $O(N^2)$ independent of $T$, for $N$ arms. The survey of Bengs et al. (2021) organizes regret and PAC (probably approximately correct) sample-complexity results by the assumptions they make about the matrix of pairwise winning probabilities. Later, Saha and Gaillard (2022) were the first to reach the optimal $O(\sum_i \log T / \Delta_i)$ against a Condorcet-winner benchmark.

Continuous convex dueling. Kumagai (2017) obtained regret $O(\sqrt{T \log T})$ with stochastic mirror descent when the cost is strongly convex and smooth, and used lower bounds from convex optimization to argue that this is optimal up to logarithmic factors; the abstract does not state the link assumption. Saha et al. (2021b) gave the query complexity when each pair yields only a single noisy comparison bit, and proved the non-stationary online convex case impossible; their 2025 paper handles general transfer functions (Saha et al., 2025). Blum et al. (2024) proved an $\Omega(d)$ lower bound under a monotone adversary.

Linear and contextual dueling. In the setting of Saha (2021), each round offers $K$ items with context features, the learner picks a subset of $q$ of them, and a noisy winner is observed. They gave an optimal $\tilde O(\sqrt{dT})$ algorithm with a matching $\Omega(\sqrt{dT})$ lower bound, and the lower bound is independent of the subset size $q$: winner feedback from a larger subset does not help. Efficient algorithms and general links followed (Saha and Krishnamurthy, 2022; Bengs et al., 2022; Di et al., 2024), and Feel-Good Thompson sampling reached a near-minimax $\tilde O(d\sqrt{T})$ (Li et al., 2024b). Wu et al. (2024) proved an $\Omega(d^{2/3} T^{2/3})$ lower bound and a matching upper bound for Borda regret, which measures an option by its average winning probability against all others. Di et al. (2025) obtained $\tilde O(\kappa d\sqrt{T} + \kappa dC)$ with $C$ adversarially flipped labels (their paper writes $\kappa$ for the smallest slope of the link, the reciprocal of ours, and so divides by it), with a nearly matching lower bound, and for the sigmoid link removed $\kappa$ from the main term. And Sekhari et al. (2023) proved that comparison queries alone can achieve regret comparable to a standard contextual bandit that observes rewards. The difference between Saha's $\sqrt{dT}$ and Feel-Good Thompson sampling's $d\sqrt{T}$ comes from the arm sets, $K$ items per round against large or continuous sets, and is not a contradiction (inference).

Reinforcement learning from preferences. For learning policies from preferences over trajectories (Section 36.1), results run from asymptotic Bayesian no-regret (Novoseller et al., 2020) and a first finite-time analysis (Xu et al., 2020a) to general function approximation (Chen et al., 2022) and a first Bayesian simple-regret guarantee (Agnihotri et al., 2026). Zhu et al. (2023) proved that under the Plackett-Luce model both the full $K$-wise maximum likelihood estimator and the one that splits rankings into pairs converge, the former asymptotically more efficiently.

29.2 The first kernelized result #

One kernel-based result came before 2021: Xu et al. (2020b) allowed both direct queries and duels, and their COMP-GP-UCB has simple regret $O(\Phi/\sqrt{T})$ after $T$ direct queries, where $\Phi$ is an information gain computed on the part of the domain that the comparisons leave as candidates for the optimum. The first kernelized dueling bound on cumulative regret, by Kirschner and Krause (2021) (Section 21.3.1), rests on assumptions that decide what it covers:

1. Feedback. Their Equation 2 is quantitative dueling feedback, $d_t = f(\vx_t^1) - f(\vx_t^2) + \xi_t$, with $\xi_t$ sub-Gaussian noise of variance proxy $\rho^2$. The model covers binary feedback only in the sense that bounded noise is sub-Gaussian.
2. Function class. $f$ lies in a known RKHS with norm at most $B$, and $k(\vx, \vx) \le 1$.
3. Regret. The sum of the utility gaps of both points of each duel.
4. Theorem 1. Regret $O\big(\sqrt{T\, \beta_{T,\delta}\,(\gamma_T + \log 1/\delta)}\big)$, roughly $\gamma_T\sqrt{T}$ for $T$ rounds (the paper writes $n$).
5. Theorem 2. On a finite domain with a unique optimum, $O\big(\Delta_{\min}^{-1}\beta(\gamma_T + \log(T/\delta))\big)$; for the linear kernel $O(\Delta_{\min}^{-1} d^2 \log(T)^2)$, and for the RBF (squared exponential) kernel $O(\Delta_{\min}^{-1} \log(T)^{2d+2})$.

The result does not cover Bernoulli outcomes under a Bradley-Terry or probit link, nor the cost $\kappa$ that such links bring; kernelized regret under the Bradley-Terry link begins with POP-BO in 2024 (inference, from the feedback model the theorems state).

29.3 Bradley-Terry bounds, 2024 to 2026 #

Four algorithms analyze the setting that PBO actually faces: Bernoulli answers whose probability is the logistic function of a utility difference (Section 16.4), with the utility in an RKHS. Section 21.3.2 introduced them; here are the theorems with their constants and conditions.

POP-BO. Xu et al. (2024b) assume a compact domain, $f$ in an RKHS, and Bernoulli feedback with $\Prob = \operatorname{sigmoid}(f(\vx) - f(\vx'))$, the logistic function of Equation (16.4). The algorithm chooses optimistically within a likelihood-ratio confidence set and uses the previous round's point as the reference point.

• Theorem 5.2. Utility regret $R_T = O\big(\sqrt{\beta_T \gamma_T T}\big)$, where $\beta_T = O\big(\sqrt{T \log(T\, \mathcal{N}(\mathcal{B}_f, 1/T, \lVert\cdot\rVert_\infty)/\delta)}\big)$ and $\mathcal{N}$ is the covering number of the function class, the number of small balls needed to cover it. For the linear and RBF kernels this gives $T^{3/4}$ times polylogarithmic factors (their Theorem 5.5). For a Matérn kernel the exponent is larger than $3/4$, and the bound is stated only for $\nu > (d/4)\big(3 + d + \sqrt{d^2 + 14d + 17}\big)$, that is, when the smoothness parameter $\nu$ is of order $d^2$.
• Theorem 5.4. The gap of the reported solution is $O\big(\sqrt{\beta_T \gamma_T}/\sqrt{T}\big)$.
• Remark 5.6. The authors suggest that preference feedback costs about an extra factor of $T^{1/4}$, on the intuition that a numerical evaluation implies a preference but not the reverse.

Later papers often abbreviate POP-BO's rate as $\tilde O((\gamma_T T)^{3/4})$; when quoting it, say that its unit is utility regret.

MaxMinLCB. Pásztor et al. (2024) frame the choice of a pair as a Stackelberg game, a game in which one player commits first and the other responds, and build preference confidence sequences for a kernelized logistic estimator. Theorem 6: with probability at least $1 - \delta$, for all $T$,

with $\beta_t = 4LB + 2L\sqrt{(2\kappa/\lambda)(\gamma_t + \log 1/\delta)}$, $\kappa = \sup_{\lvert a\rvert \le B} 1/\operatorname{sigmoid}'(a)$, and $C_3 = (8 + 2\kappa)/\sqrt{\log(1 + 4/(\lambda\kappa))}$, where $s$ is the link function, $L$ its Lipschitz constant (a bound on its slope), and $\lambda$ the regularization parameter. The regret is preference-probability regret, and "rate-optimal" in the abstract holds at most relative to GP-UCB-type analyses (inference; Section 21.3.2). Kayal et al. (2025) summarize it as $\tilde O(\gamma_T \kappa^2 \sqrt{T})$.

MR-LPF. The multi-round learning from preference-based feedback algorithm of Kayal et al. (2025) assumes $f$ in the RKHS of a known kernel with norm at most $B$, a kernel bounded by 1, the Bradley-Terry (logistic) link only, and a finite candidate set $\X$. It runs in $R \le \lceil \log_2 \log_2 T\rceil + 1$ rounds of lengths $N_1 = \sqrt{T}$ and $N_r = \sqrt{N_{r-1} T}$, picking pairs by largest kernel variance within a round and eliminating, at its end, every point whose upper confidence bound on the probability of beating some opponent is below one half.

• Theorem 4.1. There is a constant $T_0$, independent of $T$ (given in their Appendix B), such that for all $T \ge T_0$, with probability at least $1 - \delta$, $R_T \le 2CR\, \beta_{(R)}(\delta) \sqrt{\gamma_{4\lambda}(T)}\,(\sqrt{T} + 1)$, with $\beta_{(r)}(\delta) = L\big(B + \sqrt{(\kappa_r/\lambda)\log(2R|\X|/\delta)}\big)$, where $|\X|$ is the size of the candidate set $\X$ (the paper writes $N_\X$), $\kappa_1 = \kappa$, and $\kappa_r = 6$ for $r > 1$. Simplified: $\tilde O\big(\sqrt{\gamma_T T \log(|\X|/\delta)}\big)$.
• Where $\kappa$ goes. It appears only in the first round and so drops out of the main term. The paper notes that when the utility takes values in $[-5, 5]$, $\kappa$ can exceed 22,000.
• Corollary 4.5. The number of comparisons needed to find a solution with $\Prob(\vx^\star \succ \hat\vx) - 1/2 \le \varepsilon$ is $\tilde O(d \log(1/\delta)/\varepsilon^2)$ for the linear kernel, $\tilde O(\log(1/\delta)/\varepsilon^2)$ for the RBF kernel, and $\tilde O\big(\log(1/\delta)/\varepsilon^{2 + d/\nu}\big)$ for the Matérn kernel, the same order as the order-optimal sample complexity with scalar feedback.
• Tightness. The authors note that the lower bound of Scarlett et al. assumes Gaussian noise while Bradley-Terry corresponds to Gumbel noise, so a formal comparison does not strictly hold; they offer it only as an informal argument for tightness, and argue that a lower bound for preference feedback should be at least half the scalar one.

Six differences from the scalar setting should travel with any statement that MR-LPF "matches scalar Bayesian optimization" (Section 21.4.2 lists the common misreadings): the regret unit is preference probability; whether $T_0$ hides a dependence on $\kappa$ or $e^B$ has not been checked; the $\log |\X|$ comes from a union bound, so a continuous domain needs a discretization argument; the algorithm is batched and non-adaptive within a round; the optimality is an informal comparison; and every query involves two points, both counted in the regret. A machine-generated review site claims that a Loewner-order inequality used in their Theorem 4.7 may fail for small $\lambda$ (Pith, 2026); that claim is not peer reviewed and has not been confirmed by a human source, and the PF-TS paper cites MR-LPF's rate as correct.

PF-TS. Lazzaro et al. (2026) analyze Thompson sampling with preference feedback: the two points of a query are obtained by maximizing two independent posterior samples against a common anchor point. Theorem 1: with probability at least $1 - 2\delta$, $R_T = \tilde O\big(\beta_T\sqrt{T\gamma_T}\big)$ with $\beta_T = O\big(\sqrt{\gamma_T + \log(1/\delta)}\big)$, that is, $\tilde O(\gamma_T\sqrt{T})$, in preference-probability regret; $\kappa$ enters $\beta_T$ and $\gamma_T$ through a ridge term $\lambda\kappa$. The paper says the bound matches the one Chowdhury and Gopalan established for standard Thompson sampling in 2017, which is itself not order-optimal in scalar Bayesian optimization. A continuous domain must be discretized into $(B G w d T^2)^d$ points, the kernel is assumed known, and the experiments are a one-dimensional Ackley function and a catalyst data set of 63 compositions of three metals. On the Ackley function, where PF-TS had lower cumulative regret than MR-LPF and POP-BO (Section 21.3.2), MR-LPF's instantaneous regret was competitive at the horizon of 300 rounds; the two papers share authors (Vakili, Shiu).

Neural dueling bandits. Verma et al. (2025) assume $\kappa_\mu = \inf \mu'(f(\vx) - f(\vx')) > 0$ for the link $\mu$, and their result applies to Bradley-Terry, Thurstone, and exponential noise as long as stochastic transitivity holds. Their average utility regret is $\tilde O\big((\sqrt{d_{\text{eff}}}/\kappa_\mu + B\sqrt{\lambda/\kappa_\mu})\sqrt{T d_{\text{eff}}}\big)$, where $d_{\text{eff}}$ is an effective dimension built from all pairwise context differences, and the network width must be polynomial in quantities such as $T$; the authors expect the bound to be weaker than for scalar neural bandits. Oh et al. (2026a) gave $\tilde O\big(d\sqrt{\sum_t \sigma_t^2} + \sqrt{dT}\big)$ and reduced the width requirement to $\tilde\Omega(T^6)$.

29.4 The rates compared #

Table 29.1 collects the main results for continuous or kernelized preference optimization next to the scalar Bayesian optimization references: $O^*(\sqrt{T}\gamma_T)$ for GP-UCB- and GP-TS-type analyses (Chowdhury and Gopalan, 2017); $O^*(\sqrt{T\gamma_T})$ within $O(\log\log T)$ batches for batched pure exploration (BPE), near-optimal for several kernels (Li and Scarlett, 2022); and, for the Matérn kernel, lower bounds of $\Omega(T^{(\nu + d)/(2\nu + d)})$ on cumulative regret and $\Omega((1/\varepsilon)^{2 + d/\nu})$ on the simple-regret sample complexity (Scarlett et al., 2017). Here $O^*$, like $\tilde O$, hides logarithmic factors.

Preferential theory has almost reproduced scalar Bayesian optimization item by item: optimistic algorithms and Thompson sampling reach $\gamma_T\sqrt{T}$, and batched elimination reaches $\sqrt{\gamma_T T}$ (inference; Section 21.4). Whether a fully sequential preference algorithm can reach $\sqrt{\gamma_T T}$ is open. The scalar setting had a related problem, posed at COLT 2021 (Vakili et al., 2021b): whether GP-UCB itself can reach that rate. More elaborate scalar algorithms already attain it (Salgia et al., 2021), and Whitehouse et al. (2023) partly resolved the question with a sublinear bound for GP-UCB under Matérn kernels, of order $T^{(\nu + 2d)/(2\nu + 2d)}$ up to logarithmic factors, still above the lower bound; the improved information-gain rates for Matérn kernels are those of Vakili et al. (2021a), stated for $\nu > 1/2$. How much the factor $\sqrt{\gamma_T}$ between the two families matters depends on how fast $\gamma_T$ grows, which depends on the kernel (Table 13.1), and Figure 29.1 makes this concrete.

Some things to try:

• The default (Matérn 5/2, $T = 1000$). The bracket at the right shows the factor $\sqrt{\gamma_T}$ between $\gamma_T\sqrt{T}$ and $\sqrt{\gamma_T T}$. With every constant set to 1, $\gamma_T\sqrt{T}$ is still above the line $T$ at this horizon, while $\sqrt{\gamma_T T}$ is far below it: the extra $\sqrt{\gamma_T}$ is the difference between a bound that says something and one that does not, even before constants.
• Switch to the squared exponential kernel. $\gamma_T$ grows like a power of $\log T$, so asymptotically the two families differ only by polylogarithmic factors, and POP-BO's $T^{3/4}$ appears. Asymptotically it is the fastest-growing of the three, yet at these horizons it lies below $\gamma_T\sqrt{T}$ and close to $\sqrt{\gamma_T T}$: order of growth and size at a practical horizon can disagree.
• Switch to Matérn 1/2 and lengthen the lengthscale. A rough kernel makes $\gamma_T$ grow almost like $\sqrt{T}$ in one dimension, so the exponent of $\gamma_T\sqrt{T}$ is already 1 at $d = 1$. A longer lengthscale lowers $\gamma_T$ at a fixed horizon but does not change the exponents.
• Read the bottom panel for Matérn 5/2. The exponent of $\gamma_T\sqrt{T}$ is $1/2 + d/(5 + d)$, which reaches 1 at $d = 5$; the exponent of $\sqrt{\gamma_T T}$ is $(2.5 + d)/(5 + d)$, below 1 in every dimension (Exercise 21.3). POP-BO's Matérn result needs $\nu > 2.41$ even at $d = 1$, so for Matérn 5/2 it applies only in one dimension.

29.5 Link slope and regret units #

The constant $\kappa$ is the reciprocal of the smallest slope of the link over the range of utility differences the analysis allows. For the logistic link it grows exponentially with that range, because the logistic curve is nearly flat far from zero: MR-LPF's authors note that it can exceed 22,000 for utilities in $[-5, 5]$ (Exercise 21.4). Section 21.4.1 tells how scalar logistic bandits moved $\kappa$ out of the main term (Faury et al., 2020; Abeille et al., 2021), and Section 21.4.2 why utility regret and preference-probability regret are proportional only for small gaps, with the factor $1/4$ (Exercise 29.2). Two points belong here. For dueling, Di et al. (2025) (for the sigmoid link) and MR-LPF (for kernels) removed $\kappa$ from the main term, while MaxMinLCB, PF-TS, and neural dueling bandits keep it in the main term's constant; apart from the neural $\kappa_\mu$, no kernelized result gives an explicit slope dependence for a general, non-logistic link, and MaxMinLCB only remarks in a footnote that its analysis may extend to other symmetric increasing links. And POP-BO's 2024 intuition, that preferences cost an extra $T^{1/4}$, was refuted at the level of upper bounds by MR-LPF: the gap came from POP-BO's covering-number confidence width, not from preference feedback itself (inference).

29.6 Decision-theoretic results #

qEUBO (Astudillo et al., 2023) is the main Bayesian decision-theoretic result in PBO. The one-step Bayes optimal value of a query $X = (\vx_1, \dots, \vx_q)$ is $V_n(X) = \E_n\big[\max_{\vx} \E_{n+1}[f(\vx)] - \max_{\vx}\E_n[f(\vx)] \mid X_{n+1} = X\big]$, how much one more answer to $X$ is expected to raise the best posterior mean; stopping at $N$, the recommendation is $\argmax_{\vx} \E_N[f(\vx)]$; and the noisy likelihood is $L_i(f(X); \lambda) = \exp(f(\vx_i)/\lambda) / \sum_j \exp(f(\vx_j)/\lambda)$, with $\lambda = 0$ meaning noise-free answers. The four theorems and their conditions are listed in Section 28.2. Three readings of them (inference):

• Why $o(1/n)$ is fast. The conditions turn the problem into finite identification with a positive utility gap almost surely. The result says nothing about continuous domains, nor about how the rate depends on the number of options or the dimension, and it cannot be compared with frequentist simple regret of order $T^{-1/2}$.
• What the sufficient conditions exclude. An almost-sure gap bound rules out ordinary Gaussian process priors with continuous marginals, and a winning probability equal to a constant $a > 1/2$ whenever utilities differ is not the probit or logistic likelihood used in practice. The result is best read as evidence of qEUBO's consistency and a proof of qEI's inconsistency, not as a rate for practical PBO.
• No contradiction with the 2026 critiques. One-step optimality does not include multi-step or asymptotic optimality, so it does not conflict with the over-exploitation and ill-conditioning reported in two preprints (Section 28.4); on continuous domains qEUBO has neither such a result nor a frequentist regret bound.

29.7 Lower bounds #

A lower bound says how much regret every algorithm must incur on some problem in a class (Section 13.3). Without one, an upper bound cannot be called optimal.

Where order optimality is established. For finite-arm dueling bandits, the instance-dependent $\sum_i \log T/\Delta_i$ is matched by Saha and Gaillard (2022), and RMED matches asymptotically (Komiyama et al., 2015). Adversarial, batched, and weak-regret variants and the identification of Condorcet and Copeland winners also have lower bounds (Saha et al., 2021a; Saha and Gaillard, 2021; Agarwal et al., 2022; Saad et al., 2024; Haddenhorst et al., 2021a; Bengs et al., 2024), and the linear and contextual cases have the $\Omega(\sqrt{dT})$, Borda, and corruption lower bounds of Section 29.1.

How much information a query carries. Section 20.1.2 reported the finite-arm answer under the Plackett-Luce model: winner feedback from $k$-subsets has optimal sample complexity $O((n/\varepsilon^2)\ln(1/\delta))$ for $n$ arms, the same as pairs, while top-$m$ ranking feedback lowers it by a factor of $m$ (Saha and Gopalan, 2019b). The same authors gave matching instance-dependent bounds (Saha and Gopalan, 2020) and order-optimal regret $O((n/m)\ln T)$ for top-$m$ feedback and $O((n/k)\ln T)$ for full rankings (Saha and Gopalan, 2019a). In sign-feedback convex optimization, the gain from $m$-way argmin feedback is of order $\min\{\log m, d\}$ (Saha et al., 2024); for the linear Plackett-Luce model, Lee et al. (2025a) obtained $\tilde O\big((d/T)\sqrt{\sum_t 1/\lvert S_t\rvert}\big)$, with $S_t$ the subset shown in round $t$, so larger subsets provably help; and with feedback that only ranks arms by past empirical performance, no logarithmic instance-dependent regret is possible (Maran et al., 2024). The apparent conflict between "winner feedback from larger subsets does not help" and "larger subsets help" is resolved by the feedback type: more information per round needs more than the winner. For PBO, this predicts that an interface asking a person to "pick one of $K$" does no better than pairwise duels in worst-case order, while a ranking interface can; this prediction is untested for kernelized PBO (inference).

The kernelized case: no lower bound. Within our search (PMLR 2017 to 2025, NeurIPS 2017 to 2024, and a scan of 2025 and 2026), we found no algorithm-independent lower bound for kernelized preference feedback under a Bradley-Terry or probit link; targeted searches returned only scalar kernel lower bounds and finite-arm dueling lower bounds. MR-LPF's near-optimality rests on an informal comparison with the Gaussian-noise lower bound of Scarlett et al. Any preference lower bound would have to be compared with the scalar kernel lower bounds (Scarlett et al., 2017; Cai and Scarlett, 2021) and the time-varying kernel lower bound of Iwazaki and Takeno (2025). Section 21.5 lists the three kinds that are missing and what the absence means for the question whether a comparison is more expensive than a number; the only firm statement in the kernel case is that, in a batched, finite-domain setting with a warm-up period, comparisons cost at most constant and logarithmic factors more (inference).

29.8 Theory of observation models #

The skew Gaussian process theorem, and where it comes from. Three papers by Benavoli, Azzimonti, and Piga need to be told apart: the classification paper in Machine Learning volume 109 (2020) that introduced the skew Gaussian process (Benavoli et al., 2020); the GECCO 2021 Companion paper (arXiv 2008.06677) that holds the posterior theorem for PBO (Benavoli et al., 2021c); and the Machine Learning volume 110 paper (2021) that proved conjugacy to normal and affine probit likelihoods and their products (Benavoli et al., 2021a). Attributing the preference posterior theorem to "Machine Learning 2020" is therefore wrong, and "Machine Learning 2021" applies only to the general conjugacy statement.

A unified skew-normal (SUN) distribution generalizes the multivariate Gaussian by multiplying its density with a normal distribution function, which tilts it; Section 17.6 introduces it. In the theorem, $\Phi_m$ is the distribution function of $m$ independent standard normal variables, and $\Omega = D_\Omega \bar\Omega D_\Omega$ splits a covariance matrix into the diagonal matrix $D_\Omega$ of standard deviations and the correlation matrix $\bar\Omega$.

For parametric probit regression, Durante (2019) had already shown conjugacy with the unified skew-normal distribution. The theorem is exact Bayesian inference for the probit model, not a consistency or rate result. It explains why the Laplace approximation and expectation propagation misreport duel probabilities, which matters for acquisition functions that rely on predicted winning probabilities (Section 27.4), and it does not apply to the logistic link (inference). The extended skew-normal lookahead posterior of Wu and Gardner (2026) builds on it.

Posterior consistency. Posterior consistency means that the posterior concentrates on the true function as data accumulate; a contraction rate says how fast. We found no such theorem for Gaussian process preference models of the Chu-Ghahramani type. The nearest results are the frequentist confidence sets for kernelized logistic estimators in POP-BO, MaxMinLCB, and MR-LPF; qEUBO's Bayesian consistency on finite domains; and the asymptotic convergence of SelfSparring's independent-arm version.

Stochastic transitivity. The regret theorems above assume different regularity conditions on the winning probabilities, which Section 21.1.2 defines: strong, moderate, and weak stochastic transitivity, and the stochastic triangle inequality, which strong transitivity does not imply (Bengs et al., 2021). Yue et al. (2012) need strong stochastic transitivity and the triangle inequality; SelfSparring's approximate linearity is stricter than strong stochastic transitivity; the neural dueling result holds whenever stochastic transitivity holds; and the tracking results of Suk and Agarwal (2023) need the intersection of strong stochastic transitivity and the triangle inequality. Any model of a utility plus a monotone link, Bradley-Terry or probit, satisfies both at every moment (inference, derived from the definitions; Exercise 29.3). Chau et al. (2022) question the assumption of rankability; Section 27.2 reports how far their conjecture reaches.

29.9 Identifiability and aggregation #

A quantity is identifiable if different values of it produce different distributions of data, so that enough data could in principle tell them apart. A group of results shows that pairwise data are the weakest feedback when answers depend on something the model does not see.

Hidden context. Siththaranjan et al. (2024) studied a finite set of options, infinite data, uniformly sampled pairs, and an L2-regularized Bradley-Terry loss, where each answer may depend on a hidden context (who is answering, in what state) that the model does not observe:

• Theorem 3.1. Bradley-Terry preference learning implicitly aggregates hidden contexts by the Borda count: the learned utility satisfies $\hat u(a) > \hat u(b)$ if and only if $\mathrm{BC}(a) > \mathrm{BC}(b)$, where $\mathrm{BC}(a)$ is the average probability that $a$ beats a random opponent.
• Theorem 3.2. If the hidden-context noise is independent and identically distributed across options and the support of its differences contains a neighborhood of zero, the learned order equals the order of expected utility.
• Proposition 3.3. The majority preference can agree with expected utility while Bradley-Terry does not.
• Theorem 3.4. No deterministic method using infinite comparison data can always recover expected utility, even up to a monotone transformation.

The authors point out that annotators therefore have an incentive to misreport. An et al. (2026) (a preprint) also note that the Bradley-Terry-Luce loss corresponds to the Borda count. For single-user PBO, this means that if a person's answers depend on unmodeled context, such as fatigue, framing, or order, the Gaussian process utility recovers a Borda-type aggregate rather than the mean utility (inference; Exercise 29.1 works an example).

Heterogeneous people. Chidambaram et al. (2026) (AISTATS 2026; arXiv 2405.15065 and 2510.15716 are versions with the same title) proved three results about a random-coefficient logit model, in which each user has their own preference weights $\beta$:

• Lemma 4.1. If each user makes a single binary comparison, even with infinitely many users the distribution of types is not identifiable: a half-and-half mixture of $\beta$ and $-\beta$ gives probability 0.5 everywhere.
• Theorem 4.2 (restating Fox et al. 2012). If the moments satisfy the Carleman condition, the support of the features contains an open set around zero, $\beta$ is independent of the features, and there are at least 3 options, the type distribution is nonparametrically identifiable, even from incomplete rankings of three.
• Lemma 4.3. Many diverse binary comparisons by one user identify that user's $\beta$ when the matrix of feature differences has full rank.

Cycles, partial orders, and context effects. Liu et al. (2026e) proved that preferences can be represented by a reward model if and only if there are no Condorcet cycles (cases where $a$ beats $b$, $b$ beats $c$, and $c$ beats $a$ by majority), that under the Luce model Condorcet cycles appear with probability tending to 1 exponentially fast, and that Nash learning from human feedback yields a mixed strategy if and only if no response is preferred by a majority to every other. Drago et al. (2025) prove that constructing a multi-objective utility of minimal dimension compatible with a partial order of preferences is NP-hard. De Peuter et al. (2024) used a tractable surrogate of a cognitive model of preferential choice with context effects, and inferred better than Bradley-Terry variants on large-scale human data. And Cao et al. (2026) showed for a Plackett-Luce subset-choice model that learning from queries alone faces a shift-invariance barrier and needs bandit feedback as an anchor.

Taken together (inference): for regret on a single fixed utility, pairwise comparisons are not inherently more expensive than numbers in order; but for identifying a heterogeneous population, recovering expected utility under hidden context, and handling cyclic preferences, pairwise data are the weakest feedback, and ranking feedback beats winner-only feedback. The single-utility assumption behind every PBO regret bound is questioned twice over, by Chau et al.'s empirical conjecture and by Liu et al.'s asymptotic result. Section 20.5.3 and Section 20.5 take up what this means for designing queries.

29.10 Drift, contamination, response times, stopping #

Four features of real people, preferences that change, answers that are wrong, answers that take time, and sessions that must end, each have some theory, mostly outside the kernelized setting.

Drift. For finitely many arms the theory is mature. Saha and Gupta (2022) gave $O(\sqrt{KT})$ static regret against adversarial preference sequences, and dynamic regret $\tilde O(\sqrt{SKT})$ for $S$ effective switches and $\tilde O(V_T^{1/3}K^{1/3}T^{2/3})$ for continuous variation $V_T$, all with matching lower bounds, and ANACONDA (Kleine Buening and Saha, 2023) adapts to an unknown number of switches; stationary segments (Kolpaczki et al., 2022), a preprint, and change points in a high-dimensional Bradley-Terry model (Li et al., 2022) have their own results. Suk and Agarwal (2023) proved that adapting to "significant shifts" at the rate $O(\sqrt{KLT})$, with $L$ the number of significant shifts, is impossible under the Condorcet class or the strong-stochastic-transitivity class, while the intersection of strong stochastic transitivity and the triangle inequality is the largest of the common classes in which it is feasible, and Liu et al. (2026c) proved that with feedback that ranks by instantaneous utility, sublinear external regret is in general impossible, becoming possible when the total variation of the utility sequence is sublinear; Son et al. (2025) give bounds for direct preference optimization under unknown drift. For scalar kernels, Iwazaki and Takeno (2025) gave the first algorithm-independent lower bound for non-stationary kernelized bandits, and Theorem 4.1 of Bogunovic et al. (2016) shows that when the per-step change $\varepsilon$ of their Markov model is fixed, every algorithm has cumulative regret $\Omega(T\varepsilon)$. Since utility-plus-link models satisfy strong stochastic transitivity and the triangle inequality at every moment, the obstacle to tracking drift in kernelized PBO is technical, a missing dynamic regret analysis for kernels with a link, not a known impossibility (inference); with no PBO model of a drifting utility (Section 27.2), there is no dynamic regret guarantee either.

Contamination and bias. Agarwal et al. (2021) gave regret that depends linearly on the number of corrupted comparisons involving the Condorcet winner, and proved the linear dependence necessary; Saha and Gaillard (2022) pay only an additive $2C$ in the corrupted Condorcet setting. In the linear case, Di et al. (2025) gave $\tilde O(\kappa d\sqrt{T} + \kappa dC)$, with $\kappa$ multiplying the corruption term, and Oh (2026) gave $\tilde O(d(\sqrt{T} + C + D))$, where $D$ measures delays; known or unknown evaluator bias (Tang et al., 2025) and corrupted pairs in reinforcement learning from human feedback (Bukharin et al., 2024; Mandal et al., 2025) have been handled too. In the kernel case, the only robustness result remains the linear-link bias model of Kirschner and Krause 2021; the scalar reference is Bogunovic et al. (2020). Since the results of Siththaranjan et al. give annotators a reason to misreport, a mechanism for eliciting truthful feedback matters too; an AISTATS 2026 paper does this with the Vickrey-Clarke-Groves mechanism (Landolt et al., 2026), of which only the title and venue were verified.

Response times. Response time is the only human channel with theory, and only for linear utilities. Li et al. (2024a) used the EZ-diffusion model, a simplified drift-diffusion model of how evidence accumulates during a choice (Section 39.3), and showed in theory and experiment that for queries with strong preferences response times complement choices. Benkert et al. (2026) (a working paper, 2026 version) proved that binary choice frequencies identify only one point of the latent preference distribution, and that adding a monotone response-time function identifies it at several points. The Gaussian process response-time model of Shvartsman et al. (2024) has no theoretical guarantee.

Stopping. The nearest results to a stopping rule with guarantees for PBO are these. Haddenhorst et al. (2021b) combine identifying a Condorcet winner with testing whether one exists, so that the learner can stop and decline to answer, with a lower bound on the expected sample complexity and an algorithm optimal up to logarithmic factors. Shukla and Basu (2024) gave a lower bound and a matching preference-aware Track-and-Stop algorithm for vector rewards ordered by a cone. Fixed-confidence identification has its own stopping rules (Bengs et al., 2024; Saha and Gopalan, 2019b; Saha and Gopalan, 2020). Section 30.7 reports the parametric rule of Bıyık et al. and the scalar rules that have not been carried over to a pairwise likelihood.

29.11 Settled, contested, missing #

29.12 Exercises #

Further reading #

• Bengs et al. (2021) is the survey of dueling bandits, organized by the assumptions on pairwise winning probabilities; Sui et al. (2018a) is the shorter earlier survey.
• Kirschner and Krause (2021), Xu et al. (2024b), Pásztor et al. (2024), Kayal et al. (2025), and Lazzaro et al. (2026) are the kernelized results; read each theorem with its feedback model and regret unit.
• Scarlett et al. (2017) and Vakili et al. (2021a) give the scalar lower bounds and information-gain rates that every preference result must be compared with.
• Astudillo et al. (2023) is the Bayesian decision-theoretic side; its conditions repay careful reading.
• Siththaranjan et al. (2024) is the clearest account of what Bradley-Terry learning recovers when answers depend on hidden context.