Conservative Dueling Bandits: Preference Learning under Baseline Constraints

Rohan Deb; Mohammad Ghavamzadeh; Arindam Banerjee

cs.LGOct 27, 2026

Conservative Dueling Bandits: Preference Learning under Baseline Constraints

Authors: Rohan Deb, Mohammad Ghavamzadeh, Arindam Banerjee

Organizations: University of Illinois, Urbana Champaign · Qualcomm AI Research

Abstract

Contextual dueling bandits learn from pairwise comparisons, the same feedback used to fine-tune language models from human preferences. Standard algorithms explore aggressively and can show users two poor options. We study conservative contextual dueling bandits, which require that, at every round, the cumulative score of the better displayed item stay above a $(1-α)$ fraction of a trusted baseline's. An item's score is its probability of beating the best available item, so the constraint depends only on utility differences and needs no absolute rewards. This also changes how safety can be certified: we show that transferring the safety test of the conservative bandit algorithm CLUCB unchanged can incur linear regret, even when the baseline's utilities are known exactly. For linear utilities, we develop MaxInP-BC, which certifies scores through utility gaps and, when it must fall back, pairs the baseline with an informative partner so that fallback rounds still drive learning. It is safe with high probability at all times, with regret $\tilde{O}(d\sqrt{T}/κ)$ plus an additive cost of conservatism that does not grow with the horizon. For general utility classes, we develop BTIGW-BC, which turns the guarantee of an online logistic-regression oracle into cumulative safety certificates. It is safe at all times, makes finitely many fallbacks, and has sublinear regret whenever the oracle's logistic regret is sublinear. In experiments, both satisfy the constraint, which their unconstrained counterparts often violate, at a moderate cost in regret.

Figures & tables

Panel of Figure 1 — Figure 1: Linear utilities. Top: cumulative regret. Bottom: mean safety ratio $\bar{\rho}_{t}$ in (a) and worst violation in (b, c). Dashed lines mark the bar $1-\alpha$ in (a) and zero violation in (b, c); the vertical band in (a) marks the rounds where MaxInP is below the bar. Baseline-only is shown in (a) only. Intervals are $95\%$ confidence intervals over $50$ seeds. $\color[rgb]{0,1,0}\mathtt{MaxInP\mhyphen BC}$ has zero violation in every setting.

Panel of Figure 2 — Figure 2: General utilities ( $d=5$ , $|\mathcal{F}|=64$ , $q=0.10$ ), laid out as in Figure 1 with BT-IGW in place of MaxInP . $\color[rgb]{0,1,0}\mathtt{BTIGW\mhyphen BC}$ stays above the bar in (a), and its extra regret over BT-IGW arises mainly where BT-IGW violates the constraint.

Dueling Bandits

See all 16 papers

Oct 14, 2026

Replicable Dueling Bandits

Dueling bandits choose each comparison based on earlier noisy outcomes, so two runs on the same preferences can compare different pairs. We study replicable dueling bandits, where two executions with shared internal randomness and independent comparison outcomes must select the same ordered pair in every round with probability at least

1-ρ

. Building on Beat-the-Mean, whose scores change as arms are eliminated and need not rank the best arm highest, we design the first such algorithms with sublinear regret. Under relaxed stochastic transitivity with parameter

γ\ge 1

and the stochastic triangle inequality, we design an algorithm that achieves expected regret

\widetilde{O}(γ^8 K^4 H_{\mathrm{p}}/ρ^2)

, where

H_{\mathrm{p}}=\sum_{i=2}^{K}(P_{1i}-1/2)^{-1}

. Under strong stochastic transitivity, we design an algorithm based on simultaneous elimination that improves the dependence on

K

and achieves

\widetilde{O}(K^2 H_{\mathrm{p}}/ρ^2)

regret. For linear dueling bandits, we design an algorithm that achieves regret

\widetilde{O}(d^3\sqrt{T}/(c_μρ))

. Experiments on synthetic and language-model preferences show replicability, with sublinear regret.

Rohan Deb, Aadirupa Saha, Udaya Ghai +2

University of Illinois, Urbana Champaign · University of Illinois, Chicago · Amazon +1

Dueling Bandits Multi-Armed Bandits Pairwise Preference Learning

Ask PDF

Sep 30, 2026

Reserve-Aware Contrast Certificates for Conservative Bandits with Uncertain Baselines

Conservative bandits must improve an incumbent policy without exhausting a prescribed performance budget. When the incumbent is uncertain, separately bounding candidate and baseline rewards can charge twice for shared estimation error. We develop Reserve-C4B around the baseline-relative contrast itself. A shared confidence set yields an exact expression for this avoidable penalty and a tighter admissibility test at every fixed history. A reserve ledger separates statistical evidence from permitted performance deficit; a prefix-refresh extension recertifies accumulated decisions under the current confidence set without discarding previously certified credit. For linear rewards, self-normalized confidence sets provide simultaneous validity over time and adaptively generated candidates, and the resulting policy satisfies a conditional-mean performance constraint with high probability. Reproducible experiments isolate certificate coupling, prefix refresh, and historical information, showing large reductions in baseline fallback while exposing the limitations of frozen certificates.

Qinchuan Cheng

School of Automation Science and Engineering, Xi’an Jiaotong University, Xi’an, China

Multi-Armed Bandits Contextual Bandits

Ask PDF

May 7, 2026

Constrained Contextual Bandits with Adversarial Contexts

We study constrained contextual bandits with adversarial contexts, where each action yields a random reward and incurs a random cost. The conditional mean reward and cost belong to known function classes and are learned through online regression oracles. The benchmark is a stationary randomized policy whose expected cost is non-positive at every observed context. We extend the seminal

\mathsf{SquareCB}

algorithm of Foster and Rakhlin (2020), which reduces the contextual bandits to a regression problem, to the constrained setting. A surrogate reward function is constructed which penalizes the positive part of the expected cost of an action distribution, and an auxiliary variable accumulates its predicted value. Then we use an exponential Lyapunov function to control both regret and cumulative constraint violation via a single inequality. If the cumulative squared prediction error is at most

U_T

, our algorithm achieves

O(\sqrt{KTU_T})

regret and

O(\sqrt{KTU_T}\log T)

cumulative expected cost, with high probability, improving upon the previous

O(T^{3/4})

type bounds obtained in stochastic contextual settings with an unknown context distribution. Our results require neither additional margin conditions nor probabilistic assumptions on the context sequence.

Dhruv Sarkar, Abhishek Sinha

Indian Institute of Technology Kharagpur, India · Tata Institute of Fundamental Research, Mumbai, India

Contextual Bandits Adversarial Bandits

Ask PDF

Abstract

Dueling Bandits

Explore similar work

Replicable Dueling Bandits

Reserve-Aware Contrast Certificates for Conservative Bandits with Uncertain Baselines

Constrained Contextual Bandits with Adversarial Contexts