acceptodds
Under review as a conference paper at ICLR 2027

Conservative Dueling Bandits: Preference Learning under Baseline Constraints

Abstract

Contextual dueling bandits learn from pairwise comparisons, as in fine-tuning language models from human preferences. Standard algorithms explore aggressively, however, and may show users two poor options. We require that, at all times, the cumulative score of the better displayed item stay above a fraction of a trusted baseline's. An item's score is its probability of beating the best available item, so the constraint needs no absolute rewards and is invariant to utility shifts. We show that directly transferring the safety test of the conservative bandit algorithm CLUCB can incur linear regret. For linear utilities, MaxInPwBC certifies safety through utility gaps and falls back to comparisons that pair the baseline with an informative partner. It is safe with high probability at all times, with regret plus a horizon-independent cost of conservatism. For general utility classes, BTIGWBC builds safety certificates from an online logistic-regression oracle, achieving anytime safety, sublinear regret, and finitely many fallbacks. Both algorithms need only bounds on baseline scores. In experiments, both satisfy the constraint, which their unconstrained counterparts often violate, at a moderate cost in regret.

Primary area:
learning theory
Keywords:
Dueling Bandits, Preference Learning, Constrained Bandits

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_mxS1OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper considers the contextual duelling bandit problem which targets optimising action selection from qualitative human feedback signals in a form of pairwise comparisons. They follow the standard Bradley-Terry assumption in the literature which states that the comparisons are dictated by a latent utility function. The main claim of the paper is that traditional approaches such as MaxInP (Saha, 2021) explores aggressively which can lead to queries to a user between two bad choices. Instead the author propose a constrained problem where at least one of the two alternatives presented to the user is within (1−α)(1-\alpha) fraction of a known baseline utility value. The authors consider the problem under the assumption of linear utilities and more broader general class of functions and propose two algorithms, MaxInP-BC and BT-IGW-BC respectively, that can safely explore while achieving sublinear regrets. The two algorithms are extending unconstrained counterparts and numerical experiments show that they deliver on their promise of safely exploring the action space at some cost compared to the unconstrained algorithms.

Critical strengths
  1. The paper provide a reasonable regret analysis and theoretical guaranteees for the proposed algorithms
  2. The paper is well-scoped and easy to follow. Clear what are the problems the authors address and how.
  3. The paper goes beyond the linear utility assumption to provide a broader and more applicable theoretical analysis.
Critical weaknesses
  1. In section 2, the authors call their problem formulation contextual duelling bandits, however, I believe this setting is the continuous duelling bandit problem and not the contextual. In their definition, the arms are themselves are a set from a continuous dd-dimensional space, while in the standard definition by Dudik et al. (2015), the context is an auxiliary information that the bandit observes before making a selection affecting all candidate actions simultaneously.
  2. The paper lacks sufficient literature review and comparison. The authors only build on selected previous publications without addressing many more recent results of the field and do not provide sufficient comparison to previous works. One of the main claims of the paper is that duelling bandit algorithms are exploring too aggressively. While this is the case for MaxInP which relies purely on exploration, other algorithms such as POP-BO (Xu et al. 2024), MaxMinLCB (Pasztor et al., 2024), or BOHF (Kayal et al., 2025) this is less evident.
  3. The main motivation is to gather human feedback without showing only low quality options to users which would motivate a safety constraint that holds for each round of actions separately instead the authors propose a cumulative safety constraint in definition 2.1.
  4. The experimental results lack evidence of generalization. The paper does not describe the definition of the utility functions furthermore it tests the linear and general settings both only on a single utility function that does not provide sufficient evidence that their results generalize across the whole function space.
Questions for authors
  1. How do the regret bounds compare to previous works in duelling bandits and what is the additional factor due to the constraints?
  2. How do experimental results generalize to other utility functions especially in the general case, furthermore, have the authors validated performance on real world datasets to support their motivation in the introduction?
Reviewer_G5X4OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies conservative contextual dueling bandits. The authors define a score-based safety constraint (Definition 2.1, Eq. (3)) and propose two algorithms under it, MaxInP-BC for linear utilities and BT-IGW-BC for general utility classes. As the authors themselves note in Remark 2.1, any pair that contains the baseline item satisfies this constraint regardless of the other item. Exploiting this property, the algorithms adopt a straightforward "informative fallback" as their safe exploration mechanism (display the baseline together with an informative partner). Both algorithms eventually display candidate pairs that do not contain the baseline; in MaxInP-BC this decision is driven by a per-round, data-dependent certificate. The theoretical analysis is extensive (anytime safety, finite fallback counts, regret bounds). The experiments, however, are limited to synthetic data, and more importantly, they lack baselines that satisfy the proposed constraint, which makes it hard to assess the regret performance of the proposed methods.

Critical strengths
  1. The paper proposes a new problem setting (conservative dueling bandits), designs algorithms for it, and provides both analysis and experiments. The motivation through easily imaginable applications, such as presenting multiple LLM responses to a user, is appealing. (That said, for this very example the pair-average regret of Eq. (2) is not the natural objective; see Weakness 1.)
  2. Beyond analyzing the proposed methods, the paper offers theoretical insights into the problem itself, e.g., why a direct transfer of CLUCB's safety test can fail under preference feedback (Proposition A.2).
Critical weaknesses
  1. The safety constraint (Definition 2.1, Eq. (3)) is not consistent with the regret (Eq. (2)). The regret charges the average utility of the displayed pair, whereas the left-hand side of Eq. (3) takes the maximum over the pair. By using the maximum, the paper introduces a constraint that is trivially satisfied by any pair containing the baseline, so that the learner can explore freely with the other item of the pair at zero safety cost. Exploration is supposed to be the central difficulty of conservative bandits; a definition that makes exploration trivially safe substantially reduces the significance of the proposed setting. In addition, the paper has no related-work section and does not discuss existing alternatives such as stage-wise (per-round) baseline constraints (e.g., Khezeli & Bitar, AAAI 2020; Moradipari et al., NeurIPS 2020), which are directly relevant to this design choice.

  2. The experiments contain no baseline that satisfies the proposed constraint other than the trivial baseline-only policy. The authors' own informative fallback is itself a trivially feasible policy under Definition 2.1 and, in terms of regret, dominates the baseline-only (self-duel) policy, so it should be reported as the natural reference point. More importantly, since safety is nearly free under this constraint, the contribution of the proposed methods lies in when they stop displaying the baseline, and this should be evaluated against simple alternatives. At minimum, an ablation that runs informative fallback for an initial phase and then switches to unconstrained MaxInP (or BT-IGW) should be included. Other natural candidates are the CLUCB transfer, which the paper itself defines (Definition A.1, and the alternative baseline-centered test in Eq. (36), Remark A.2) but never runs, and a stage-wise certificate (accept the candidate pair only when ct≤2−4(1−α)st(xbt)c_t \le 2 - 4(1-\alpha)s_t(\mathbf{x}_{b_t}), i.e., Algorithm 1 without the accumulated budget). Without such comparisons, the reported "cost of conservatism" (1.39× for MaxInP-BC and 2.69× for BT-IGW-BC, Section 5) cannot be interpreted.

Questions for authors
  1. Why does the left-hand side of Eq. (3) take the maximum over the displayed pair, while the regret in Eq. (2) charges the average utility of the pair? Under the maximum, any pair containing the baseline item satisfies the constraint regardless of its partner (Remark 2.1). Is an average-based (or minimum-based) version of the constraint tractable in this setting, given that a baseline self-duel is uninformative (Remark A.1)?

  2. The constraint in Eq. (3) is cumulative, so the surplus accumulated during fallback rounds can later be spent on candidate pairs with large certificates ctc_t (Algorithm 1, line 5). Is this intended behavior? Did the authors consider a stage-wise (per-round) version of the constraint, and if so, why was the cumulative version preferred?

  3. In Algorithm 2, line 5, the acceptance test Qt−1+ht≥GIGW(t)/4Q_{t-1}+h_t \ge G_{\mathrm{IGW}}(t)/4 appears to depend only on tt and on the baseline scores si(xbi)s_i(\mathbf x_{b_i}) (through Qt−1Q_{t-1}, hth_t, and the envelope GIGW(t)G_{\mathrm{IGW}}(t) defined in Eq. (13)), and not on the observed outcomes oto_t or on the oracle's predictions f^t\hat f_t. Is this correct? If so, BT-IGW-BC is equivalent to a fixed schedule that displays fallback pairs for an initial phase and then runs unconstrained BT-IGW. How does this differ from the fallback-then-switch ablation suggested in Weakness 2?

  4. Please report the number of fallback rounds NTN_T and the time of the last fallback for each experimental setting. Theorems 3.1 and 4.1 are stated in terms of NTN_T, and Figures 1 and 2 do not show it. This would also help to interpret the comparison with the informative-fallback-only and fallback-then-switch references suggested in Weakness 2.

  5. Why are different β\beta-multipliers used for MaxInP (0.02) and MaxInP-BC (0.05) (Section 5)? After the last fallback round, MaxInP-BC with the same βt\beta_t coincides with MaxInP, yet the regret gap in Figure 1(a) keeps widening over the entire horizon. Please report MaxInP and MaxInP-BC with the same multiplier, or separate the multiplier used for the certificate ctc_t from the one used for the promising set Ct\mathcal C_t, so that the cost of the constraint can be distinguished from the cost of a wider confidence ellipsoid.

  6. Safety is evaluated through the cross-seed mean ρˉt\bar\rho_t (Section 5, Protocol), whereas Theorems 3.1 and 4.1 guarantee the constraint for each trajectory with probability at least 1−δ1-\delta. Please report per-seed statistics, e.g., the fraction of seeds in which Eq. (3) is violated at any prefix t≤Tt \le T, and the worst per-seed violation.

Reviewer_NkjGOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper looks at contextual dueling bandit under constraints. Instead of allowing sufficient exploration, the approach requires the arms to be pulled each time is at least almost as good as a baseline's arm. The paper builds upon the BTL model and studies both linear utilities and generalize to other families of utilities. Sub-linear regret bounds have been derived. Experiments on a limited scale of comparison are provided as well.

Critical strengths
  • This paper studies an important scenario of dueling bandit under budget constraint.

  • The regret analysis seems to be valid for both linear and generalized family of utility functions.

Critical weaknesses
  • The reviewing had a difficult time starting to read the abstract. Many terms were not defined, e.g., what are the score, utility shifts, horizon-independent, anytime safety, and the terms in the convergence rate? Similarly, when reading the contribution lists, many notations were introduced without definitions.

  • Related to the previous comment, the appendix is ill organized. Current they are simply a list of math results, with very little discussions on their physical meanings, or a clear roadmap on how they led to the core math result. Also, the numbering of the equations is inconsistent.

  • The paper misses important related work discussion, as well as comparison in the experiments. There have been quite many studies on dueling bandits under constraints, an just to name a few [1-2]. Yet the paper fails to discuss these important references. Also, the experiment is based on a very limited scale of comparison, where the methods are compared to their unconstraint counterparts.

[1] Deb et al., ``Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resources'', AISTATS 2024.

[2] Yang et al, ``A reduction-based framework for conservative bandits and reinforcement learning'', ICLR 2022.

Questions for authors

See weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.