Dueling Bandits and the Theory of Comparisons

Chapter 19 built a loop that learns from duels and asked how to choose the next pair. It did not ask how good any rule for choosing pairs can be. That question belongs to bandit theory, which Chapter 13 introduced for ordinary evaluations: an algorithm is scored by its regret, the total shortfall of what it chose compared with the best choice, and a good algorithm is one whose regret grows slowly. This chapter asks the same question for comparisons.

The question turns out to have a twist that ordinary bandits do not have. With numbers, "the best option" is the one with the largest value. With duels, it is the one that wins, and wins against whom is not always a consistent notion: preferences can go in a circle, as in rock, paper, scissors. So the chapter begins with what "best" can mean, then follows the algorithms that find it among finitely many options, then moves to the continuous, kernelized setting that preferential Bayesian optimization (PBO) lives in, where the bounds of 2021 to 2026 are, and ends with what is still unproved.

21.1 Dueling bandits #

The dueling bandit problem was posed for search engines. Suppose an intranet search system ships with $K$ built-in ranking functions and must find the best one for a new customer. Asking users to rate result lists is unreliable, but a trick called interleaving merges the results of two rankers into one list and infers from the user's clicks which ranker they preferred. Each query to the system is then a duel between two rankers, and the system pays every time it shows results from a worse ranker (Yue et al., 2012; Yue and Joachims, 2009).

Formally, there are $K$ options, called arms as in Section 13.2. In each round $t$ the algorithm picks two arms $a_t$ and $b_t$, possibly the same, and observes which one wins. Arm $i$ beats arm $j$ with an unknown probability $P_{ij}$, with $P_{ji} = 1 - P_{ij}$ and $P_{ii} = 1/2$. The $K \times K$ matrix $\mathbf{P}$ of these probabilities is everything there is to know, and the algorithm never sees it, only the outcomes of the duels it chooses. It is convenient to measure each probability from one half: $\Delta_{ij} = P_{ij} - 1/2$, positive when $i$ tends to beat $j$.

When the preferences come from a utility, as in Equation (19.1) or the Bradley-Terry model of Section 16.4, $P_{ij}$ is a link function of the utility difference, and everything in this section is simple: the arm with the highest utility beats every other arm. The dueling bandit formulation does not assume a utility. It starts from the matrix, which is more general, and that generality is why the next question has more than one answer.

21.1.1 What "best" can mean #

The most natural definition asks for an arm that beats everyone.

The name comes from voting theory, where a Condorcet winner is a candidate who beats every other candidate in a head-to-head vote. There is at most one, but there may be none. If A beats B, B beats C, and C beats A, no arm beats everyone. Three weaker definitions always produce an answer (Sui et al., 2018a).

Each definition answers a slightly different question. A Copeland winner counts victories and ignores their margins, so it exists and coincides with the Condorcet winner when there is one, but it may still lose to some arms. A Borda winner weighs margins, so it can differ from the Condorcet winner even when one exists: an arm that beats everyone narrowly can have a lower average than an arm that loses to it narrowly and crushes everyone else (Sui et al., 2018a; Urvoy et al., 2013; Jamieson et al., 2015). A von Neumann winner is not a single arm but a mixture, the optimal strategy of the zero-sum game in which each player picks an arm and the payoff is $P_{ij} - 1/2$. Von Neumann's minimax theorem guarantees that one exists, and when a Condorcet winner exists, the von Neumann winner puts all its weight on it (Dudík et al., 2015; Sui et al., 2018a).

Two of these have already appeared in this book under other names. The soft-Copeland score that González et al. (2017) maximize (Section 19.2) is the average probability of winning against a uniformly random opponent, so despite its name it is the continuous version of the Borda score. And the Borda count appeared in Section 20.5.3: when people with different hidden preferences are pooled into one Bradley-Terry model, the fitted utility ranks options by their Borda counts (Siththaranjan et al., 2024).

The figure below lets you build a non-transitive tournament and watch the definitions part ways.

Some things to try:

• Set the cycle strength c to 0. The matrix comes from a utility, so A beats everyone: it is the Condorcet winner, the Copeland winner, the Borda winner, and the von Neumann winner, all at once (Exercise 21.1).
• Raise c past about 1. B now beats A, C beats B, and A still beats C. The Condorcet winner disappears, A, B, and C tie on Copeland score, A keeps the highest Borda score because it crushes D and E, and the von Neumann winner becomes a mixture of the three. At the default of 1.5, it puts the most weight on B (Exercise 21.2 explains the pattern).
• Set c back to 0 and switch to "A narrow champion". A beats every arm with probability 0.55, and B beats C, D, and E with probability 0.9. A is the Condorcet and Copeland winner, but B is the Borda winner: the average rewards B's large margins.
• Flip a pair at the bottom. Make E beat D. Nothing changes at the top: the definitions disagree only when the strong arms do.

21.1.2 Transitivity, and regret #

How much structure a preference matrix has is described by conditions of stochastic transitivity, which extend "if A beats B and B beats C, then A beats C" to probabilities. For arms with $\Delta_{ij} \ge 0$ and $\Delta_{jk} \ge 0$, strong stochastic transitivity requires $\Delta_{ik} \ge \max\{\Delta_{ij}, \Delta_{jk}\}$, moderate requires $\Delta_{ik} \ge \min\{\Delta_{ij}, \Delta_{jk}\}$, and weak only $\Delta_{ik} \ge 0$. A separate condition, the stochastic triangle inequality, requires $\Delta_{ik} \le \Delta_{ij} + \Delta_{jk}$ for arms in the order $i \succ j \succ k$; it is not implied by strong transitivity (Bengs et al., 2021). Any model of the form "utility plus a monotone link", Bradley-Terry and Thurstone included, satisfies strong stochastic transitivity, because the winning probability grows with the utility difference; and since these links are concave for positive differences, they also satisfy the triangle inequality (inference, from the definitions; Exercise 21.1).

Whether real preferences violate transitivity is contested. Chau et al. (2022) placed a Gaussian process on a skew-symmetric preference function, one that can represent cycles, and found it more accurate than the utility model of Chu and Ghahramani (2005) on chameleon contests, NFL games, and a citation graph, concluding that violations are common; these are data sets in which intransitivity is expected, and none is a single person's design preference (Section 27.2). A 2026 result, about many annotators judging the responses of language models, shows that preferences can be represented by a single reward function if and only if they contain no Condorcet cycle, and that under a Luce model of the population such cycles exist with probability converging to one exponentially fast (Liu et al., 2026e). For one person judging designs, a utility remains the working assumption of this book.

With a definition of the best arm comes a definition of regret. When a Condorcet winner, call it arm 1, exists, the regret of a duel between $a_t$ and $b_t$ is how much more often the winner would have beaten them,

the formulation of Yue et al. (2012). It can be read as the fraction of users who would have preferred the best ranker to the two that were shown. A duel of the winner against itself costs nothing, so a learner that has found the winner can stop paying. Without a Condorcet winner, regret is measured against a Copeland winner: with normalized Copeland scores $\zeta_i$ (the fraction of other arms that $i$ beats), a duel costs $\max_i \zeta_i - (\zeta_{a_t} + \zeta_{b_t})/2$ (Zoghi et al., 2015; Wu and Liu, 2016).

Dueling bandits are harder than ordinary bandits in one specific way. The algorithm pays for the arms it plays, but it observes only how those two arms compare with each other, never how either compares with the unknown best arm. Learning that both are bad requires duels between other pairs (Sui et al., 2018a).

21.2 Algorithms #

Dueling bandit algorithms come in two styles (Sui et al., 2018a). Most are asymmetric: they pick a reference arm, the current champion or a plausible winner, and then a challenger to test against it. Some are symmetric: two copies of the same learner each pick one arm, as two players of a game would.

21.2.1 Interleaved Filter #

The first algorithm, Interleaved Filter (Yue et al., 2012), works like a tournament with a reigning champion. It picks a candidate at random and duels it against every remaining arm in turn. Any arm that loses to the candidate with high confidence is eliminated; as soon as an arm beats the candidate with high confidence, that arm becomes the new candidate. When one arm is left, the algorithm plays it against itself for the rest of the run. It assumes that the arms have a total order, that strong stochastic transitivity holds, and that the triangle inequality holds. Under these assumptions its version IF2 has expected regret of order $(K/\varepsilon_{1,2}) \log T$, where $\varepsilon_{1,2} = \Delta_{12}$ is the margin between the two best arms, and Yue et al. (2012) prove that every algorithm suffers regret of order $(K/\varepsilon)\log T$ on some problems, with $\varepsilon$ the smallest margin of the best arm. IF2 is optimal up to a constant factor.

21.2.2 Relative upper confidence bounds #

RUCB (Zoghi et al., 2014) carries the optimism of UCB1 (Section 13.2.3) to duels and needs only one assumption: that a Condorcet winner exists. It keeps counts $W_{ij}$ of how often $i$ has beaten $j$ and forms an optimistic estimate of every winning probability.

The champion is an arm that could still be the Condorcet winner; the challenger is the arm most likely to prove that it is not. RUCB has a finite-time regret bound of order $K \log T$ plus a constant that grows like $K^2$ (Zoghi et al., 2014; Sui et al., 2018a).

The best possible rate is known exactly. Komiyama et al. (2015) proved an asymptotic lower bound for every algorithm, a sum over suboptimal arms in which each contributes $\log T$, weighted by the regret of the cheapest duel that exposes it and divided by a Kullback-Leibler divergence between Bernoulli distributions (Section 6.2), and gave an algorithm, RMED, that matches it asymptotically (Sui et al., 2018a). Saha and Gaillard (2022) were the first to reach the optimal finite order $\sum_i \log T / \Delta_i$ against a Condorcet winner, which they describe as resolving a long-standing problem.

21.2.3 Thompson sampling, twice #

Thompson sampling (Section 13.2.4) carries over just as naturally. Double Thompson Sampling (D-TS) (Wu and Liu, 2016) keeps a Beta posterior on every winning probability $P_{ij}$, starting from Beta(1, 1), and samples twice. The first sample of the whole matrix picks the arm with the highest sampled Copeland score, among the arms whose optimistic Copeland score is highest. A second sample picks the challenger: the arm most likely to beat the first, among arms not already known to lose to it. Because it targets Copeland winners, it works with or without a Condorcet winner. Its regret is of order $K^2 \log T$ for general Copeland problems, and a simplified version reaches $K \log T + K^2 \log\log T$ when a Condorcet winner exists (Wu and Liu, 2016). Copeland winners also have their own optimistic algorithms with bounds of order $K \log T$ under mild assumptions (Zoghi et al., 2015) and an asymptotically optimal algorithm (Komiyama et al., 2016).

The figure runs simplified versions of RUCB and Double Thompson Sampling on the matrices of Figure 21.1, together with random pairs, and plots the cumulative Copeland regret.

Some things to try. At the default, with A as the Condorcet winner, both curves bend over like a logarithm, and Double Thompson Sampling ends lower: about 30 against about 70 for RUCB after 2000 duels, while random pairs pay about 1000. Move the cycle strength to 1.5. Now A, B, and C share the Copeland title, no arm beats every other arm even optimistically once enough data arrive, and RUCB's champion step falls back to a random arm in most rounds: its regret grows in a straight line, past 200 at 2000 duels. Double Thompson Sampling keeps bending. Then choose "A narrow champion" with the cycle strength at 0: the winner beats everyone with probability 0.55, a margin of 0.05, and both algorithms are still paying hundreds after 2000 duels. The $1/\Delta$ in every bound above is this effect: a narrow margin takes many duels to resolve.

21.2.4 Sparring, and the first uses with people #

The symmetric style treats the two arms as two players. SelfSparring (Sui et al., 2017b) draws each arm of the duel (or each of several arms, for multi-dueling) from the same Thompson sampling posterior, so the algorithm duels against itself; with a Gaussian process prior over the arms it can share information between similar arms. Its theory is thinner than its use. It assumes "approximate linearity", a winning probability that is approximately a linear function of the utility difference, which the authors call more restrictive than strong stochastic transitivity; it proves convergence to the best arm for independent arms and an asymptotically optimal rate $O(K\ln T/\Delta)$; and the authors write that a finite-time guarantee would require a more refined analysis and that an analysis of the kernelized version is lacking.

These algorithms have run with people in the loop. CorrDuel, a dueling bandit for large sets of correlated options, chose spinal cord stimulation settings in a live clinical trial, which its authors describe as the first application of an online learning algorithm to spinal cord injury treatment (Sui et al., 2017a). CoSpar tuned exoskeleton gaits with the posterior sampling of SelfSparring, adding coactive feedback in which the user also suggests improvements (Tucker et al., 2020b); Chapter 24 follows that line of work.

21.2.5 Beyond a list of arms #

Two extensions lead toward the continuous problem. For a continuous, convex problem, the original dueling bandit paper of Yue and Joachims (2009) proposed gradient descent from duels, and Kumagai (2017) proved regret of order $\sqrt{T\log T}$ for strongly convex, smooth costs, optimal up to logarithmic factors. For linear utilities over $d$ features, Saha (2021) gave an algorithm with regret of order $\sqrt{dT}$ (up to logarithmic factors) for choosing subsets and observing their winner, and a matching lower bound that does not depend on the subset size: the winner of a larger subset does not help, the finite-dimensional counterpart of Section 20.1.2.

21.3 Kernelized dueling #

PBO is a dueling bandit with infinitely many arms, one for every point of a continuous domain, and with a utility $f$ that is smooth. The analysis of Section 13.4 handled the same jump for ordinary evaluations by replacing the number of arms with the maximum information gain $\gamma_T$ (Definition 13.3) and by assuming that $f$ belongs to the reproducing kernel Hilbert space (RKHS) of a kernel, a space of functions built from kernel bumps, with a norm bound $\lVert f\rVert_k \le B$ that limits how rough $f$ can be (Section 13.4.4; Section 10.2.4 says what the bound assumes). Kernelized dueling bandits make the same two moves.

What is learned from a duel is a difference, $h(\vx, \vx') = f(\vx) - f(\vx')$. A function on pairs needs a kernel on pairs, and Section 18.1 already derived it: when $f \sim \GP(0, k)$, the difference $h$ is a Gaussian process on pairs whose covariance is the preference kernel, there written with $g$ for the utility. The bandit literature calls it the dueling kernel:

Adding a constant to $f$ leaves $h$ unchanged, and the dueling kernel is blind to it, the shift invariance of Section 18.4. The analyses below state their rates in terms of the information gain of $k^D$ or of $k$, and the two grow at the same rate (Pásztor et al., 2024; Kayal et al., 2025). When the eigenfunctions of $k$ average to zero under the input distribution, as for a stationary kernel on a circle, each eigenvalue of the dueling kernel is exactly twice one of $k$; on an interval they do not, and the correspondence is not exact (Section 10.3).

21.3.1 The first kernelized bound #

Kirschner and Krause (2021) gave what they describe as the first efficient kernelized dueling bandit algorithm with a cumulative regret guarantee, an information-directed sampling rule. Their feedback model is quantitative: a duel returns $f(\vx_1) - f(\vx_2) + \xi$, the utility difference plus sub-Gaussian noise (noise whose tails are no heavier than a Gaussian's), and covers binary answers only in the sense that a binary answer is a bounded noisy observation. With $f$ in an RKHS of norm at most $B$ and $k(\vx, \vx) \le 1$, the regret, summed over both points of each duel, is of order $\sqrt{T\beta_T(\gamma_T + \log 1/\delta)}$, roughly $\gamma_T\sqrt{T}$ after $T$ rounds. Their motivation was robustness: in Bayesian optimization with a bias common to both evaluations, such as drift in the system being tuned, the difference cancels the bias, and the bound stays sublinear even when the bias is unbounded. The model is not the Bradley-Terry or probit one, so the bound does not pay the cost that the nonlinear link adds below (inference, from the stated feedback model). An earlier result combined duels with direct evaluations (Xu et al., 2020b).

21.3.2 Bradley-Terry bounds, 2024 to 2026 #

Four results analyze the model this book uses for comparisons, a Bernoulli answer whose probability is the logistic function of the utility difference, $\Prob(\vx \succ \vx') = \operatorname{sigmoid}\big(f(\vx) - f(\vx')\big)$ with $\operatorname{sigmoid}(a) = 1/(1 + e^{-a})$, the link of Equation (16.4) with $\tau = 1$. Each builds a confidence set for $f$ from a kernelized logistic regression and chooses pairs by optimism, elimination, or sampling. They differ in what they assume and in the unit in which they count regret. The next four paragraphs are a reference for readers of those papers. On a first reading, go to Table 21.1, which holds what the rest of the chapter uses.

POP-BO (Xu et al., 2024b) chooses the next point optimistically against the previous one. Its regret, counted in utility, is $O(\sqrt{\beta_T\gamma_T T})$, where its confidence width $\beta_T$ itself grows like $\sqrt{T}$ times the square root of the logarithm of a covering number, a count of how many functions are needed to approximate every function in the class. For linear and squared exponential kernels this gives $T^{3/4}$ times polylogarithmic factors; for Matérn kernels, the result holds only when the smoothness $\nu$ exceeds $(d/4)\big(3 + d + \sqrt{d^2 + 14d + 17}\big)$, which is of order $d^2$. The authors read the extra factor as the price of preference feedback, roughly $T^{1/4}$, on the grounds that scalar evaluations imply preferences but not the reverse.

MaxMinLCB (Pásztor et al., 2024) treats choosing a pair as a game between a leader and a follower: the leader picks a point that does well even against the follower's best response, both judged by lower confidence bounds. It counts regret in preference probability: a duel costs $\big(\Prob(\vx^\star \succ \vx_t) + \Prob(\vx^\star \succ \vx'_t) - 1\big)/2$, zero when both points are optimal. Its Theorem 6 gives, with probability at least $1 - \delta$ and for all $T$ at once, $R_T \le C_3\,\beta_T\sqrt{T\gamma_T} = O(\gamma_T\sqrt{T})$, where $\beta_T$ grows like $\sqrt{\gamma_T}$ and the constant $C_3 = (8 + 2\kappa)/\sqrt{\log(1 + 4/(\lambda\kappa))}$ contains the link-slope constant $\kappa$ of Section 21.4.1 and the regularization weight $\lambda$ of the kernelized logistic regression. The abstract calls the guarantee rate-optimal; it is $O(\gamma_T\sqrt{T})$, not $O(\sqrt{\gamma_T T})$, a factor $\sqrt{\gamma_T}$ above the best known rates, so "rate-optimal" holds at most relative to GP-UCB-type analyses (inference). The analysis also restricts the choice to a set of plausible maximizers.

MR-LPF (Kayal et al., 2025) takes the batched route of scalar Bayesian optimization. It runs in at most $\lceil\log_2\log_2 T\rceil + 1$ rounds of growing length; within a round it duels pairs of maximal uncertainty among the surviving candidates, without looking at the answers, and at the end of a round it eliminates every candidate whose optimistic chance of beating some other candidate is below one half. It assumes $f$ in an RKHS of norm at most $B$, the logistic link, and a finite candidate set $\X$ of size $|\X|$. Its Theorem 4.1 holds for $T \ge T_0$, a warm-up length that does not depend on $T$ and is specified in the paper's appendix, and simplifies to

in preference-probability regret, where $\tilde O$ hides logarithmic factors. The link-slope constant enters only the first round, so it drops out of the leading term. This is the same order as the best scalar results, which contradicts POP-BO's reading at the level of upper bounds: the $T^{1/4}$ came from POP-BO's covering-number confidence width, not from preference feedback itself (inference). The authors note that the matching scalar lower bound assumes Gaussian noise while the Bradley-Terry model corresponds to Gumbel noise, so they offer the comparison as an informal argument for tightness, not a proof.

PF-TS (Lazzaro et al., 2026) is Thompson sampling for preferences: two independent posterior samples are each maximized against a common anchor point. With probability at least $1 - 2\delta$ its regret, in preference probability, is $\tilde O(\beta_T\sqrt{T\gamma_T})$ with $\beta_T = O(\sqrt{\gamma_T + \log(1/\delta)})$, that is, $\tilde O(\gamma_T\sqrt{T})$, which the authors note matches the bound of Chowdhury and Gopalan (2017) for scalar Thompson sampling. A continuous domain is handled by a discretization, and the kernel is assumed known. On a one-dimensional Ackley function (300 rounds, 30 runs) its cumulative regret was lower than MR-LPF's and POP-BO's and comparable to MaxMinLCB's; the PF-TS and MR-LPF papers share two authors.

A fifth line replaces the kernel with a neural network. Neural dueling bandits (Verma et al., 2025) hold for Bradley-Terry, Thurstone, and other links as long as stochastic transitivity holds, with a bound in average utility regret that depends on an effective dimension and on the minimum slope of the link, and that the authors expect to be weaker than its scalar neural counterpart.

All of these analyze frequentist estimators, kernelized logistic regression with confidence sets, and algorithms built for the analysis. None analyzes the pipeline practitioners run, a Laplace-approximated Gaussian process posterior with EUBO (Section 19.5), whose guarantees are the one-step Bayes optimality and finite-domain consistency of Section 19.4.1 (inference).

21.4 The rates, side by side #

Table 21.1 puts the kernelized results next to each other with the scalar results they echo. Two scalar references matter: GP-UCB and GP-TS analyses give $O^*(\gamma_T\sqrt{T})$ (Chowdhury and Gopalan, 2017), and a batched pure exploration algorithm reaches $O^*(\sqrt{\gamma_T T})$ within $O(\log\log T)$ batches, near-optimal for several kernels (Li and Scarlett, 2022), where $O^*$ hides logarithmic factors. The full table, with the finite-arm and neural results, is Table 29.1.

The pattern is that preferential theory has reproduced scalar theory almost item by item: optimism and Thompson sampling reach $\gamma_T\sqrt{T}$, as GP-UCB and GP-TS do, and batched elimination reaches $\sqrt{\gamma_T T}$, as its scalar model does (inference). Whether a fully sequential preference algorithm can reach $\sqrt{\gamma_T T}$ is open. For scalar feedback, sequential algorithms that reach it exist (Salgia et al., 2021); what was posed as an open problem at COLT 2021 is whether GP-UCB itself can (Vakili et al., 2021b), and that has been partly resolved (Whitehouse et al., 2023).

The factor $\sqrt{\gamma_T}$ between the two families matters most in higher dimensions. For a Matérn kernel with smoothness $\nu > 1/2$ in $d$ dimensions, $\gamma_T$ grows like $T^{d/(2\nu + d)}$ up to logarithmic factors (Vakili et al., 2021a), the last row of Table 13.1, so $\gamma_T\sqrt{T}$ grows like $T^{1/2 + d/(2\nu + d)}$. For the common Matérn 5/2 kernel the exponent is $1/2 + d/(5 + d)$, which reaches 1 at $d = 5$: from five dimensions on, the sequential bounds no longer say that regret grows more slowly than $T$, and so say nothing. The exponent of $\sqrt{\gamma_T T}$ is $(\nu + d)/(2\nu + d)$, below 1 in every dimension and equal to the exponent of the scalar lower bound of Scarlett et al. (2017) (inference, our arithmetic on the stated rates; Exercise 21.3). The figure draws both.

21.4.1 The slope of the link #

The constant $\kappa$ that appears in several bounds measures how flat the link function can get. A duel between a much better and a much worse option is almost always won by the better one, so its answer is almost certain and carries little information about how much better it is. Where the logistic curve is flat, large changes in the utility difference produce small changes in the answer, and learning there is slow. The constant is the reciprocal of the smallest slope of the link over the range $[-D, D]$ of utility differences the analysis must allow:

It grows exponentially with the range. Near zero the logistic slope is $1/4$, so $\kappa$ is at least 4; if utilities may lie anywhere in $[-5, 5]$, differences reach 10 and $\kappa$ exceeds 22,000 (Kayal et al., 2025). A bound with $\kappa$ in its leading term can therefore be vacuous for realistic ranges even when its dependence on $T$ looks good.

Scalar logistic bandits met the same problem first. Faury et al. (2020) showed that earlier guarantees of order $\kappa\sqrt{T}$ could be improved to order $\sqrt{T}$ with $\kappa$ only in a second-order term, and Abeille et al. (2021) proved a problem-dependent lower bound of order $d\sqrt{T/\kappa}$ with a matching upper bound: where the link is flat, the problem can even be easier, because answers there are predictable. For duels, Di et al. (2025) removed $\kappa$ from the leading term for linear utilities with the sigmoid link, and MR-LPF did so for kernels; MaxMinLCB, PF-TS, and neural dueling bandits keep it there.

21.4.2 The unit of regret #

The table mixes two units, and they are not interchangeable. Utility regret counts $f(\vx^\star) - f(\vx_t)$, how much utility was lost. Preference-probability regret counts $\Prob(\vx^\star \succ \vx_t) - 1/2$, how much more often the best option would have won. The second saturates: a terrible option and a bad one both lose almost surely, so both cost almost $1/2$, while their utility losses can differ by any amount.

Statements that a preferential algorithm is of the same order as scalar Bayesian optimization usually compare preference-probability regret with scalar utility regret. Near the optimum, where gaps are small, the comparison is fair up to the factor 4; far from it, the factor grows with the gap, to about $2D$ at the largest one (inference).

21.5 What is missing #

A lower bound says how much regret every algorithm must pay on some problem, and so whether an upper bound can be improved (Section 13.3). For duels among finitely many arms they are known: the bounds of Yue et al. (2012) and Komiyama et al. (2015) above, matched by algorithms. For linear utilities they are known too: order $\sqrt{dT}$ for choosing subsets with winner feedback, whatever the subset size (Saha, 2021). For the kernelized problem with a Bradley-Terry or probit link, the one PBO poses, we found no algorithm-independent lower bound as of September 2026 (Section 29.7).

The scalar problem has them. For a Matérn kernel, every algorithm suffers cumulative regret of order at least $T^{(\nu + d)/(2\nu + d)}$ on some function of bounded RKHS norm, and needs at least $(1/\varepsilon)^{2 + d/\nu}$ evaluations to find an $\varepsilon$-optimal point (Scarlett et al., 2017). The only bridge to comparisons is the informal argument of Kayal et al. (2025): if two noisy evaluations are turned into one comparison by keeping only which is larger, the comparison cannot be more informative than the two evaluations, so a preference lower bound should be at least half the scalar one under the matching noise. The scalar bound assumes Gaussian noise, and the Bradley-Terry model corresponds to Gumbel noise, so the argument is not a proof.

Three lower bounds are missing, in order of how much their absence limits the theory (inference): a lower bound for kernelized duels under a nonlinear link; a lower bound that says how the slope constant $\kappa$ must enter kernelized preference regret; and a kernelized lower bound for rankings and choices from sets, which would say whether the finite-arm finding of Section 20.1.2, that only richer answers than the winner help, carries over.

So is a comparison more expensive than a number? The honest answer depends on the setting (inference). For finitely many arms and for linear utilities, dueling rates match the rates for numerical rewards up to constants and the link factor. For kernels, the best upper bounds have the same order, under the assumptions of MR-LPF, and no lower bound says whether that is tight. And one binary answer carries at most one bit while a noisy number carries only a limited amount too, so equal rates do not mean equal information per query.

Chapter 29 reports this theory in full, including drift, contamination, response times, and the identifiability results behind Section 20.5.3.

21.6 Exercises #

Further reading #

• Yue et al. (2012) define the K-armed dueling bandit problem, its regret, and Interleaved Filter, with the matching lower bound.
• Sui et al. (2018a) survey the algorithms (IF, RUCB, MergeRUCB, RMED, D-TS, Sparring, SelfSparring) and the alternative winners; Bengs et al. (2021) is the longer survey, organized by assumptions on the preference matrix.
• Zoghi et al. (2014) and Wu and Liu (2016) are the original RUCB and Double Thompson Sampling papers; Zoghi et al. (2015) treats Copeland winners.
• Kirschner and Krause (2021), Pásztor et al. (2024), Kayal et al. (2025), and Lazzaro et al. (2026) are the kernelized bounds, each stating its feedback model and regret unit precisely.
• Scarlett et al. (2017) gives the scalar lower bounds that any preference lower bound will be compared with; Faury et al. (2020) explains the link-slope constant in logistic bandits.