Conservative Dueling Bandits: Preference Learning under Baseline Constraints

Rohan Deb; Mohammad Ghavamzadeh; Arindam Banerjee

Source-linked AI summary

Conservative Dueling Bandits: Preference Learning under Baseline Constraints

Rohan Deb, Mohammad Ghavamzadeh, Arindam Banerjee

arXiv:2610.36708v1Oct 27, 2026cs.LGcs.AIstat.ML

TL;DR

Preference-based learners need to explore without repeatedly showing users poor options, but numerical-reward safety certificates do not directly fit pairwise feedback. This paper develops baseline-constrained methods using utility-gap and online-oracle certificates; both are safe at all times with high probability, and experiments show constraint satisfaction at a moderate regret cost.

Problem
Contextual dueling bandits lack a baseline-constrained framework for ensuring that cumulative scores of displayed options stay close to a trusted policy using only pairwise preference feedback.
Source: §1 · p. 2, §2 · p. 4
Method
MaxInP-BC certifies linear-utility scores through utility gaps and informative baseline fallbacks, while BTIGW-BC turns online logistic-regression guarantees into cumulative score certificates.
Source: §1 · p. 3, §3 · p. 3
Results
Both conservative methods satisfy the baseline constraint at every round in experiments, while their unconstrained counterparts often violate it early, at a moderate added regret cost.
Source: §4 · p. 3
Takeaways & Limitations
Preference-score constraints can be enforced from binary comparisons without absolute rewards, while fallback comparisons can continue to support learning.
Source: §1 · p. 3, §6 · p. 13
Beyond the Bradley–Terry–Luce model, scores would need to be defined against a von Neumann winner.
Source: §6 · p. 14

Abstract

from arXiv · show

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-\alpha)$ 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}/\kappa)$ 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.

1. Introduction

Pairwise preferences offer a more consistent alternative to absolute ratings, and contextual dueling bandits model learning from such comparisons. This paper adds a cumulative baseline constraint and develops methods to enforce it without relying on absolute rewards.

Motivation

Pairwise comparisons are easier and more consistent to collect than absolute ratings, motivating preference learning across search, recommendations, and human-in-the-loop design.Pairwise preferences are also used to fine-tune language models.Source: §1 · pp. 1–2

Why new certificates are needed

Transferring CLUCB’s safety test unchanged can incur linear regret, even when baseline utilities are known exactly.The unchanged test certifies cumulative candidate rewards, while comparisons leave uncertainty about common utility levels.Source: §1 · pp. 2–3

Linear utilities

MaxInP-BC certifies scores through utility gaps and, on fallback, pairs the baseline with an informative partner so learning continues.Any pair containing the baseline is safe under the score constraint, regardless of its partner.Source: §1 · p. 3

Framework

The proposed constraint keeps the cumulative preference score of the better displayed item above a (1 −α) fraction of the baseline’s at every prefix, without absolute reward observations.The score-based constraint is invariant to utility shifts.Source: §1 · p. 3

General utility functions

BTIGW-BC converts online logistic-regression guarantees into cumulative score certificates and updates its oracle on candidate and fallback comparisons.For realizable classes with sublinear oracle logistic regret, it provides anytime high-probability safety and sublinear regret.Source: §3 · p. 3

Experiments

In experiments, both conservative methods satisfy the baseline constraint at every round, while unconstrained counterparts often violate it early.The added regret is moderate and concentrated where the constraint is tight, compared with always playing the baseline.Source: §4 · p. 3

2. Problem Formulation

The paper formulates contextual dueling bandits with binary preference feedback and a trusted baseline. Its constraint compares cumulative scores of the better displayed items with baseline scores at every prefix.

Interaction model

At each round, the learner selects an ordered pair from the context set and receives noisy binary feedback indicating which item was preferred.In the stated LLM setting, the pair corresponds to two responses shown to a user.Source: §2 · p. 3

Preference model

Under the BTL model, pairwise preference probabilities are logistic functions of latent utility differences, so adding a constant to every utility changes no comparison probability.A self-duel has success probability 1/2 and provides no information about the utility function.Source: §2 · p. 4

Assumptions

The model assumes bounded utility differences, and the linear case uses an unknown bounded-norm parameter with bounded-norm contexts.For linear utilities, the stated utility-difference bound can be B = 2LS.Source: §2 · p. 4

Regret

Regret is the cumulative gap between the best item’s utility and the average utility of the two compared items.The instantaneous regret is defined from that same best-item-versus-pair-average gap.Source: §2 · p. 4

Baseline performance constraint

The baseline performance constraint requires the cumulative preference score of the better item in each displayed pair to remain at least a (1 −α) fraction of cumulative baseline scores.The item score is its probability of beating the round’s best item; the constraint uses preference probabilities, not realized comparison labels.Source: §2 · pp. 4–5
The score-based constraint compares preference probabilities along the learner’s trajectory, and any pair containing the baseline has score at least the baseline’s.This leaves the other item available for information acquisition.Source: §2 · p. 5

3. Linear Utilities: Conservative Maximum-Informative-Pair

MaxInP-BC uses linear utility structure to select informative pairs while maintaining a cumulative baseline-safety budget. Its certificates bound score performance through utility gaps, and fallback comparisons continue to inform learning.

Algorithm

MaxInP-BC fits a regularized likelihood model, forms a confidence ellipsoid and promising-item set, then proposes the most informative pair for safety testing.If rejected, it displays the baseline with the promising partner having the largest comparison width.Source: §3 · pp. 5–6

Confidence and certificates

The algorithm’s confidence ellipsoid contains the true linear parameter simultaneously at all rounds with probability at least 1 −δ.This event supports both item selection and the safety certificate.Source: §3 · p. 5
On the confidence event, the width of the promising set bounds candidate regret, and utility-gap certificates yield lower bounds on the displayed pair’s score.The score bound follows from the fact that the better available item has score 1/2 without estimating any utility.Source: §3 · p. 6

Fallbacks

Fallback pairs contain the baseline, preserving at least its score, while the informative partner retains at least half the candidate width.The fallback partner’s regret is controlled by the same certificate used for candidate decisions.Source: §3 · p. 7

Safety budget

The safety budget accepts a candidate only when its proposed update preserves nonnegativity; fallback updates add a lower bound on their actual surplus.Candidate and fallback updates are computed before observing the comparison outcome.Source: §3 · pp. 7–8

Guarantees

With probability at least 1 −δ, MaxInP-BC is α-conservative at every horizon, has at most Ncons fallbacks, and has regret at most G(T) + 1/2∆hNcons.For fixed L, S, and λ, the additive conservatism term is independent of T, while the leading regret term has the same dependence on d and T as unconstrained MaxInP.Source: §3 · pp. 8–9
Every fallback time is bounded by the certificate envelope and conservatism parameters, yielding at most Ncons fallbacks.The fallback count is also at most T.Source: §3 · p. 8

Why not transfer CLUCB directly

Directly transferring CLUCB’s unchanged certification rule can incur Ω(T) regret with high probability, even with exact baseline utilities.Comparison confidence sets accumulate differences, whereas average utilities depend on pair averages; the proposed method instead certifies through utility gaps.Source: §3 · p. 9

4. General Utility Functions

For general utility classes, BTIGW-BC uses an online logistic-regression oracle to certify safety cumulatively, while keeping fallback comparisons informative. Under the stated realizability and oracle-regret conditions, it provides anytime high-probability safety, regret control, and finitely many fallbacks.

4. General Utility Functions

BTIGW-BC converts online logistic-regression guarantees into cumulative score certificates and updates the oracle on candidate and fallback comparisons.Without a confidence ellipsoid for certifying candidates individually, it displays a candidate only when accumulated score credits cover it; otherwise, it pairs the baseline with an IGW-drawn partner.Source: §4 · p. 9
With probability at least 1 − δ, the oracle’s cumulative regret is bounded by GIGW(t) for every t ≥ 1.The envelope follows under Assumptions 1, 2, and 5.Source: §4 · p. 10
Cumulative credits cover candidate charges, while baseline-containing fallback comparisons earn positive credits and retain an informative partner.The safety accounting lower-bounds cumulative surplus by credits minus candidate-round regret charges.Source: §4 · pp. 10–11
Under Assumptions 1, 2, 3, and 5, Algorithm 2 is α-conservative simultaneously for every T with probability at least 1 − δ, and its fallback count is bounded by min{T, NIGW}.The regret bound is stated in terms of GIGW(T) in the theorem passage.Source: §4 · p. 11
For finite classes, the stated cost of conservatism is independent of T.The remark gives A_F ≡ eB log |F|/κ + 1/κ^2.Source: §4 · p. 11

5. Experiments

Across the reported sweeps, both conservative algorithms have zero violation, while their unconstrained counterparts violate the constraint in most settings. The experiments show a regret cost for conservatism that can disappear under looser constraints.

Experiments

Each configuration runs for T = 10^4 rounds on 50 independent instances, with tuning on seeds disjoint from those reported.Safety in the reported experiments is empirical because the tuned multipliers fall outside the theory.Source: §5 · p. 12

Linear utilities

MaxInP-BC has zero violation across the linear-utility sweeps, while MaxInP violates the constraint in all but the loosest setting.At d = 10, K = 50, α = 0.05, and q = 0.14, MaxInP-BC’s mean safety ratio stays at or above 0.991 at 1.39× MaxInP’s regret.Source: §5 · p. 12

General utilities

BTIGW-BC has zero violation across the general-utility sweeps, while BT-IGW violates the constraint in every setting.In the reported configuration, BTIGW-BC stays at or above a 1.014 mean safety ratio at 2.69× BT-IGW’s regret.Source: §5 · p. 13, Figure 2 · p. 13

6. Conclusion

The conclusion presents conservative contextual dueling bandits as a way to keep cumulative preference scores above a trusted baseline while learning from comparisons. It reports anytime high-probability safety for linear and general utility classes and an additive cost of conservatism.

6. Conclusion

Both proposed methods are safe at all times with high probability, and conservatism adds only an additive regret term.The conclusion identifies MaxInP-BC for linear utilities and BTIGW-BC for general utility classes.Source: §6 · p. 13

A.3. Anytime logistic confidence ellipsoid

With probability at least 1 −δ, the confidence event bounds the estimator error simultaneously for every time t.The stated event is ∥θ̂_t − θ⋆∥_Vt ≤ β_t for all t ≥ 1.Source: §A.3 · p. 21

A.4. The promising set and the regret certificate

The promising set is nonempty for every round, and its items have a bounded utility gap from the best item on the confidence event.The supplied passages state nonemptiness and the gap result, but do not include the full bound.Source: §A.4 · pp. 21–22

A.5. Elliptical potential and the certificate envelope

The cumulative certificate envelope bounds the accumulated certification costs using the widths of the comparison vectors.The appendix uses an elliptical-potential bound to control these widths.Source: §A.5 · pp. 23–24

A.6. Safety, fallback count, and regret

The appendix establishes an anytime safety, fallback-count, and regret guarantee for the linear-utility method. It also shows that fallbacks occur only during a finite initial period and gives a simplified sublinear-rate statement.

A.6. Safety, fallback count, and regret

The number of fallbacks is finite because G(t) = o(t), so the condition 4αs t < G(t) holds for only finitely many t.Each fallback time satisfies that condition.Source: §A.6 · p. 25
With probability at least 1 −δ, every prefix is α-conservative, the fallback count is at most min{T, Ncons}, and regret is at most G(T) + 1/2 ∆hNcons.All three guarantees hold simultaneously for every T ≥ 1.Source: §A.6 · p. 26

A.7. The simplified rate

Back-substitution yields the stated simplified regret rate, while the theorem’s G(T) bound remains the exact nonasymptotic statement.The simplified display is an order statement only.Source: §A.7 · p. 26

Construct the confidence set

The confidence-set construction illustrates why directly transferring CLUCB’s cumulative certification rule can fail under preference feedback. The proposed comparison-based certificates instead use utility gaps and informative fallbacks to control certification error.

Construct the confidence set

The direct CLUCB certification rule can force a linear number of fallbacks, which implies linear regret on the constructed instance.The proposition concerns a two-dimensional instance satisfying the stated assumptions; the cited passage also notes that every displayed pair satisfies both constraints.Source: Construct the confidence set · pp. 28, 30

Known baseline utilities permit the identity

Utility-gap certificates and informative baseline fallbacks keep cumulative certification error bounded by G(T) along the comparisons actually observed.The connection between certification and information acquisition yields the finite-fallback guarantee.Source: Known baseline utilities permit the… · p. 32

A.10. Relaxing knowledge of baseline scores

The relaxed variant replaces exact baseline-score knowledge with valid lower and upper score bounds available before each round. Deterministically valid bounds preserve the original guarantees, and a known gap bound can remove the need for any baseline-score estimate.

A.10. Relaxing knowledge of baseline scores

Valid lower and upper bounds on the baseline score suffice for the modified safety test, making exact score knowledge optional.The bounds must be available before the round-t pair is selected and cover the context-dependent baseline score simultaneously over time.Source: §A.10 · pp. 32, 38
Deterministically valid bounds preserve the exact guarantees and confidence level of Theorem 3.1.The theorem’s probability accounting also allows statistical bounds with an additional failure-probability term.Source: §A.10 · p. 33
With a known upper gap bound ∆h, the method needs the baseline item but no exact or estimated baseline score.The deterministic bounds give δb = 0 and retain Theorem 3.1’s bounds and confidence level.Source: §A.10 · p. 37

Appendix B. Analysis for General Utility Functions

The analysis allows arbitrary predictable context sets and conditions the Bradley–Terry–Luce comparison law on information available before the outcome; it does not use absolute baseline utility.

The analysis covers arbitrary predictable context sets, including the main paper’s i.i.d. model.Source: Appendix B · p. 38
The BTL comparison law is conditioned on information available before the comparison outcome.Source: Appendix B · p. 38
The analysis assumes B > 0, K ≥ 2, and uses no absolute baseline utility.Source: Appendix B · p. 38

B.1. Adapting C-SquareCB to preference feedback

Preference feedback does not support cardinal calibration from logistic predictions, and even zero observed margin error can leave plug-in scores miscalibrated. The analysis instead links certification to observed comparison gaps and sampling, including baseline-partner fallbacks.

B.1. Adapting C-SquareCB to preference feedback

Logistic margin error does not control individual utility errors, so C-SquareCB’s cardinal calibration cannot be invoked, although preference scores remain shift invariant.Source: §B.1 · p. 39
For α = 1/4, zero observed margin error can coexist with a plug-in score above the 3/10 threshold when the true pair score falls below it.The example is conditional on the displayed pairs, not a regret lower bound for an IGW algorithm or a claim about every comparison.Source: §B.1 · p. 39
The construction updates the oracle with candidate and fallback comparisons; fallbacks pair the baseline with a sampled partner, though a fallback may still be a self-duel.Certification uses the error of the comparison actually observed, and including the baseline makes each fallback safe directly.Source: §B.1 · pp. 39–40

B.2. The fixed-partner IGW inequality

The fixed-partner IGW inequality bounds true regret using estimated gaps and comparison error, without restricting the absolute levels of the values.The distribution assigns at least 1/K probability to its estimated maximizer.Source: §B.2 · pp. 40–41

B.3. From logistic regret to predictable margin error

The analysis converts logistic-oracle regret into a simultaneous predictable margin-error bound, then builds an epoch envelope that includes fallback comparisons. Under sublinear logistic regret, the resulting envelope grows sublinearly.

B.3. From logistic regret to predictable margin error

The uniform predictable error bound holds simultaneously for every prefix under any predictable comparison-sampling rule, with probability at least 1 − 2δ′/3.The proof uses logistic-loss decomposition, curvature on the bounded margin range, and concentration for label noise.Source: §B.3 · pp. 41–42

B.4. An epoch envelope including fallback comparisons

The epoch envelope covers candidate and fallback decisions because it uses the error of the comparison actually displayed on either branch.Candidates use two independent draws from the sampling distribution; fallbacks pair the baseline with one draw.Source: §B.4 · p. 43

B.5. Combining epochs and controlling growth

Restarting the oracle by doubling-length epochs while preserving credits yields a nondecreasing envelope, and sublinear logistic regret implies GIGW(t) = o(t).Fallback labels enter the oracle because their errors control their partners’ gaps through the same inequality used on candidate rounds.Source: §B.5 · p. 44

B.6. Safety, fallback count, and regret

The analysis establishes prefix safety, finitely many fallbacks, and regret bounds from the oracle envelope. It also gives a finite-class specialization, permits baseline-score bounds instead of exact scores, and describes a known-horizon version without oracle restarts.

B.6. Safety, fallback count, and regret

The certificate remains nonnegative at every prefix, so cumulative true surplus stays nonnegative and the score constraint is safe throughout.The argument preserves credits across oracle restarts; a fallback adds baseline surplus credit.Source: §B.6 · p. 45
The algorithm makes finitely many fallbacks, with a horizon-independent total bound NIGW determined by problem parameters and the oracle-regret function.The bound is uniform in T.Source: §B.6 · pp. 45–46
When the oracle envelope is sublinear, the regret bound is sublinear; the displayed specialization has an additive conservatism contribution that can be bounded independently of the stopping horizon.The result holds simultaneously for every T on an event of probability at least 1 − δ.Source: §B.6 · p. 46

B.7. A finite-class oracle and explicit specialization

For a finite class, the oracle has logistic regret Rlog(n) = e^B log |F|, and for B = 1 the specialization has AF = O(log |F| + 1).Computing the sampling distribution takes O(K) arithmetic after the K score evaluations; the oracle’s computational cost is separate.Source: §B.7 · pp. 47–48

B.8. Relaxing baseline-score knowledge

Baseline-score bounds Lt and Ut can replace exact baseline scores while retaining the safety and regret guarantees when they cover the scores at every round.The overall guarantee probability is at least 1 − δ − δb; deterministic bounds have δb = 0.Source: §B.8 · p. 48

B.9. A known-horizon version without oracle restarts

The known-horizon version avoids oracle restarts but uses horizon-dependent parameters; the epoch construction additionally provides a uniform total-fallback bound.Source: §B.9 · p. 48