Conservative Dueling Bandits: Preference Learning under Baseline Constraints

Introduction

Many learning systems that interact with people cannot rely on numerical rewards. When users are asked to rate a search result, a recommended item, or a piece of generated text on an absolute scale, the scores they give are noisy, poorly calibrated across individuals, and expensive to collect at scale. Asking the same users which of two options they prefer is easier for them and yields a more consistent signal [23]. This has motivated a large body of work on learning from pairwise preferences [4, 15, 2] (Yue et al. 2012; Wirth et al. 2017). Its applications include online evaluation and optimization of search rankers [22, 6, 19] (Radlinski et al. 2008; Yue and Joachims 2009), recommender systems [23] (Kalloori et al. 2016), human-in-the-loop design [5, 18] (Tucker et al. 2020), and learning from human comparisons [7], which has more recently become a standard way to fine-tune language models, either by reinforcement learning against a learned reward model [1] (Ziegler et al. 2020; Stiennon et al. 2020; Ouyang et al. 2022) or by optimizing the policy directly on the preference data (Rafailov et al., 2023).

The dueling bandit problem gives a clean abstraction of this interaction and has been studied for finitely many actions (Yue et al., 2012). In each round, the learner selects a pair of actions, presents them to a user, and observes only a noisy binary outcome indicating which one was preferred. Because no single observation reveals how good an action is, the learner must infer quality from patterns of wins and losses. A common way to add structure is to posit a probabilistic choice model. Under the Bradley–Terry–Luce (BTL) model [4, 20] (Luce 2005), each action has a latent utility, and the probability that one action beats another is a logistic function of their utility difference (cf. Assumption 1). The Plackett–Luce model extends this to comparisons among more than two items (Zhao et al., 2020). Contextual dueling bandits (Saha, 2021) let the utility also depend on observed side information, such as a query, a user profile, or a prompt. They have led to algorithms with sublinear regret guarantees for linear and more general utility classes, the latter typically through reductions to online regression oracles (Sekhari et al., 2023), an approach that extends to neural function classes in contextual bandits with cardinal rewards [8]. Constraints are far less understood under preference feedback. For dueling bandits with knapsack constraints, Deb et al. [9] show that relative feedback makes the problem harder than its bandit counterpart: without further assumptions on the budget, it is not learnable from a regret-minimization perspective.

However, all of this work measures performance by regret against the best comparison in hindsight. The resulting algorithms therefore explore as aggressively as they can. This sits uneasily with how preference-based learners are deployed in practice, because every comparison is shown to a real person. A user who is repeatedly offered two unappealing recommendations, or two unhelpful answers, has little reason to keep trusting the system, however informative those comparisons are for the learner. Moreover, a new learning system rarely starts from scratch. It usually replaces or augments an existing policy whose behavior is considered acceptable. In such settings, it is natural to require that algorithms avoid aggressive exploration, and ensure that the deployed policy performs at least comparably to an existing, trusted baseline strategy. Concretely, we ask that at every step, the better of the two displayed items be, in aggregate, at least a $(1-\alpha)$ fraction as good as what the baseline would have offered.

For bandits with numerical rewards, this kind of safe exploration is captured by conservative bandits [16] (Wu et al. 2016; Kazerouni et al. 2017). Conservative algorithms are now available for linear rewards under both optimism and Thompson sampling [11] (Kazerouni et al. 2017), and for general reward classes accessed through online regression oracles [10]. These methods keep a budget of permissible loss relative to the baseline: they lower-bound the cumulative reward of the actions played so far, credit the baseline’s reward on rounds where it is played, and explore only when this bound stays above the target. That bookkeeping requires knowing how good the learner’s actions are in absolute terms, and preference feedback does not provide it. A comparison reveals only the difference between two utilities, so a confidence set built from comparisons can leave the overall level of utility uncertain no matter how much data arrives. A lower bound on cumulative utility computed from such a set may then stay loose indefinitely. Indeed, we show that transferring CLUCB’s safety test unchanged can incur linear regret, even when the baseline’s utilities are known exactly. As with knapsack constraints [9], relative feedback changes what a constrained learner can certify. This shapes both the constraint and how it is enforced. We measure each item by its probability of beating the best available item, which depends only on utility differences, and we certify safety through utility gaps rather than estimated payoffs. A second difficulty arises when the budget runs out. A conservative bandit then plays the baseline, but the dueling analogue, showing the baseline against itself, yields a fair coin flip and no information. A learner that falls back this way stops learning exactly when it is uncertain enough to need the fallback. Because our constraint scores a pair by its better item, any pair containing the baseline is safe whatever its partner. We therefore pair the baseline with an informative partner, so that fallback rounds still sharpen the certificates that govern future exploration.

In this work, we study Preference Learning under Baseline Constraints. Our technical contributions are as summarized below.

1. Framework: We formulate conservative contextual dueling bandits under Bradley–Terry feedback, requiring the cumulative preference score of the better displayed item to remain above a $(1-\alpha)$ fraction of the baseline’s at every prefix. This score-based constraint is invariant to utility shifts and requires no absolute reward observations.

2. Linear utilities: We show that a direct CLUCB transfer can incur linear regret and develop MaxInP-BC, which certifies scores through utility gaps and uses informative baseline fallbacks. We prove anytime high-probability safety and regret $\widetilde{O}\left(d\sqrt{T}/\kappa+\Delta_h d^2/(\kappa^2\alpha^2s^2)\right)$, where $s=\sigma(-\Delta_h)$. The additive conservatism term is independent of the horizon, and known score bounds suffice in place of exact baseline scores.

3. General utility functions: We develop BTIGW-BC, which converts online logistic-regression guarantees into cumulative score certificates and updates the oracle on both candidate and fallback comparisons. For realizable classes with oracle regret $\mathcal{R}_{\log}(T)=o(T)$, we prove anytime high-probability safety and regret $\widetilde{O}\left(\sqrt{KT\left[\mathcal{R}_{\log}(T)/\kappa+1/\kappa^2\right]+\Delta_hK\left[\mathcal{R}_{\log}(T)/\kappa+1/\kappa^2\right]/(\alpha^2s^2)}\right)$.

4. Experiments: On synthetic linear and general-utility instances, MaxInP-BC and BTIGW-BC empirically satisfy the baseline constraint at every round. Their unconstrained counterparts violate it in early rounds in nearly all settings. Conservatism costs some extra regret over the unconstrained learners, concentrated where the constraint is tight, but far less than the linear regret of always playing the baseline.

Problem Formulation

We consider a stochastic Contextual Dueling Bandit (CDB) problem. At each round $t\in[T]$, the learner is presented with a context set $S_t=\{x_{t,1},\ldots,x_{t,K}\}\subset\mathcal{D}$ of $K$ items (or arms), where each $x_{t,i}$ is drawn i.i.d. from an unknown distribution $\mathcal{P}_{\mathcal{D}}$ over a decision space $\mathcal{D}\subset\mathbb{R}^d$. The agent selects an ordered pair $(x_t,y_t)\in S_t\times S_t$ (repetitions are allowed), and receives noisy binary feedback $o_t\in\{0,1\}$ indicating which item is preferred. In the context of LLMs, $(x_t,y_t)$ correspond to the two responses shown to the user, and $o_t$ to the user’s recorded preference. Let $\mathcal{H}_t$ denote all information available immediately before observing $o_t$, including all completed rounds, the current contexts and baseline information, and the selected pair. As in Saha (2021); Bengs et al. [3]; Li et al. (2024), we assume preferences are generated by a latent utility function $f:\mathcal{D}\to\mathbb{R}$, through the Bradley–Terry–Luce (BTL) model.

Two structural properties of (1) will be useful. The comparison law depends only on utility differences and is invariant to adding a constant to every utility. A self-duel has success probability $1/2$, so its outcome provides no information about $f$.

Let $\mathbf{x}_t^\star\in\arg\max_{\mathbf{x}\in\mathcal{S}_t}f(\mathbf{x})$ denote a best item in round $t$, ties broken by a fixed rule. Next we define the regret of an algorithm following Saha (2021); Verma et al. (2025). It captures the cumulative gap between the best possible utility and the average utility of the learner’s choices over $T$ rounds.

Regret. Suppose an algorithm chooses the pair $(\mathbf{x}_t,\mathbf{y}_t)$ at time $t\in[T]$. The instantaneous regret incurred at round $t$ is the gap between the utility of the best item and the average utility of the compared pair, denoted $R_t:=f(\mathbf{x}_t^\star)-\frac{1}{2}(f(\mathbf{x}_t)+f(\mathbf{y}_t))$, and the cumulative $T$-round regret is

Next we define a performance constraint that the algorithm must satisfy so that the overall user experience stays above a threshold set by an existing trusted baseline policy.

Assumption 3 (Baseline Gap and Bounds) Let $\Delta_{t,b_t} := f(x_t^\star) - f(x_{b_t})$ denote the baseline gap. There are known constants $0 \le\Delta_l \le\Delta_h \le B$ with $\Delta_l \le\Delta_{t,b_t} \le\Delta_h$ for all $t \in[T]$; equivalently

Remark 1 (Why the maximum and why scores) The constraint in (3) compares cumulative preference probabilities along the learner’s trajectory, rather than realized comparison labels. Using the maximum ensures that any pair containing the baseline has score at least that of the baseline, allowing its partner to be selected for information acquisition.

Linear Utilities: Conservative Maximum-Informative-Pair

Assumption 4 (Linear Utility) There is an unknown $\theta^\star\in\mathbb{R}^d$ with $\lVert\theta^\star\rVert_2 \le S$ such that $f(\mathbf{x}) = \langle\theta^\star,\mathbf{x}\rangle$, and $\lVert\mathbf{x}\rVert_2 \le L$, for every $\mathbf{x} \in\mathcal{D}$. The learner optimises over $\Theta= \{\theta: \lVert\theta\rVert_2 \le S\}$, so Assumption 2 holds with $B = 2LS$ and $\kappa= \sigma(B)(1-\sigma(B))$.

In the unconstrained setting, MaxInP (Saha (2021)) maintains a set of items that may still be optimal and displays the most uncertain pair among them. Such a pair is informative, but nothing prevents both of its items from being poor. We therefore design MaxInP-BC around a safety budget. The algorithm fits $\theta^\star$ by regularized maximum likelihood on the observed comparisons and uses the resulting confidence ellipsoid to identify promising items. It then proposes the most informative pair and displays it only if the baseline constraint remains certifiably satisfied. Otherwise, it falls back to a pair that contains the baseline item and is still informative for learning.