Efficient and Near-Optimal Algorithm for Contextual Dueling Bandits with Offline Regression Oracles

Thanks a lot for your careful reading and insightful comments.

W1: Some notational clarification:

• Line 54, 55: Will fix repeated expression in L54 and the expression of Fig2 in L55
• Line 108: Please note we clarified this in L107, $o_t \in \{0,1\}$ is the binary preference feedback
• $p(i,j)$: Yes, note $p \in \Delta_{K \times K}$ is a joint distribution over item pairs. Hence $p(i,j) \in [0,1]$ denotes the probability of $(i,j)$-th pair in $p$.
• Equation (2): Will correct the typo by changing $b \to a$ in the 1st term of Eq2.
• Lines 174-175: Note we mentioned $p \in \Delta_{K \times K}$ (eg L166, L173), so $p$ is always a joint distribution. Will clarify more if needed.
• Lines 176-184: For any two mixed strategies $p \in \Delta_K$ and $q \in \Delta_K$, $q^\top M p$ denotes the expected probability of $q$ winning over $p$. So a +ve value represents that $q$ is a stronger policy than $p$ and vice-versa. [9,13] also gives a detailed explanation of Nash (Von Neumann) policies of symmetric two-player 0-sum games, as referenced. Will add more details to improve the readability of the remark.
• ${\psi}^{\star}$ in Assump3: Thanks for catching this. ${\psi}^{\star}$ represents "Best-Response Policy", we will add a reference (Defn6, A.3) to it in Assump 3.
• Line 290: Yes, $\sigma$ refers to the sigmoid function, as clarified in the objective, L125.

Many thanks for pointing them out, will clarify all of them in the update.

Q1: The Final two lines in the proof of Cor4: This is a standard analysis in the regret analysis of epoch-based contextual bandit algorithms, e.g., please see the last steps of the derivation provided in [30] for their proof of Cor1 (or even Thm1) to see the final steps. We will also add a few extra lines of derivation in our proof of Cor4 (C.5) to make the proof clearer.

Q2: Deriving pure $\tilde O(\sqrt{dT})$ regret bound for the continuous case: Yes, absolutely. When $\kappa$ is the $\ell_2$ ball of radius 1 and every $\phi \in \Phi$ is 1-$\ell_2$ norm bounded (ie. $\forall x \in \mathcal X, ~||\phi(x)||_2 \leq 1$), using the simple vanilla least-square regression oracle will yield the desired $\tilde O(\sqrt{dT})$ regret bound. We will add this as a corollary to analyze some special cases of Thm9 (same as Cor4). Thanks again for the great suggestion!

We hope this addresses all of your concerns. We are happy to clarify any further questions and respectfully urge the reviewer to reconsider the final evaluation in light of the rebuttal.

Dear Reviewer czBn,

We sincerely appreciate your time, thoughtful evaluation. As the discussion phase is now active and the decision deadline approaches, we wanted to kindly follow up on our rebuttal.

We hope our responses addressed your concerns as well, and we would be truly grateful for any additional feedback or follow-up questions you may have.

If any points remain unclear or merit further discussion, we would be more than happy to elaborate. We believe that a brief exchange at this stage could help resolve any remaining uncertainties and potentially contribute to a more favorable outcome.

Thank you once again for your time and consideration—we greatly value your input.

Thanks, Authors

Thanks a lot for your careful reading and insightful comments.

W1: Computation Complexity

Please see Q3 of Reviewer g3ya.

W2: Experiments:

Please see Q1 of Reviewer g3ya.

Q1. IBR Assumption:

Assumption 3 posits the existence of one or more “good” items that strictly outduel every other item and are equally strong among themselves. Concretely, the class of preference matrices ({P}) must allow for a “best set” of actions that tie each other and simultaneously outscore all remaining actions.

Example of IBR but not RUM or SST:

There are many such examples. Any random utility based model follows SST by design, so $RUM \subset SST$. But $SST \subset IBR$ and the class of IBR is much larger than SST. E.g., any preference relation with a strong Condorcet winner automatically satisfies the IBR property, without having any transitivity relation; assume a preference matrix $P \in [0,1]^{K \timed K}$ s.t. $1 \leftarrow \arg\max_{i \in [K]}P(i,j), ~ \forall j \in [K]$ (hence 1 is also a CW). Another example is having a equally strong set of top-cycle arms $\mathcal C \subset [K]$ s.t. $P(i,j) = 0.5 ~\forall i,j \in \mathcal C$ and for any $i \in \mathcal C$ and $j, j' \in [K] \setminus \mathcal C$, $P(i,j) > P(j',j)$. Again such top-cycle class of preferences need not have any transitivity and can easily violate SST throughout.

Thanks for bringing this up, we will add these examples in the paper (remark after Assump3).

Note IBR holds by default for the Continuous decision space setting. Since RUM-like preference structures automatically satisfy the condition of having a best (or set of best) item(s), Assumption 3 trivially holds in our continuous setting (Alg. 2). Thus, in large or potentially infinite action spaces where utility-based models are commonplace, the assumption naturally remains valid and helps maintain the same recursion-based analysis as in the finite-armed case.

Q2: ``efficient or practical way to define and implement the function class used in this work"

To the best of our understanding, there might be some misunderstanding on the reviewer's part since we can define $\mathcal M$ as broadly and generally as we want it to be based on the requirement/ complexity of the underlying preference environment. We have discussed multiple such functions classes (and the choice of efficient regression oracles for the corresponding We discussed several examples of such hypothesis preference classes in $\mathcal M$ in A.3 and Cor 4).

Note such hypothesis‑class premise is identical to many (highly cited) contextual‑bandit work (ILTCB, SquareCB, FALCON) and in classical supervised‑learning settings such as linear and generalized‑linear regression, RKHS models, and deep networks (see [17, 30], Li et al. ’22, Zhu et al. ’22, Blum et al. ’21).

It's important to note that, despite the primary theoretical focus of our work, the assumption is also not restrictive in practice since the algorithm designer is free to choose $\mathcal{M}$! It can be arbitrarily rich—finite sets, GLMs, RKHS classes, Banach spaces, or deep networks that approximate Sobolev‑ball functions (Farrell ’21). Of course, any theoretical guarantee will require some structural assumptions for provable guarantees, but Realizability is a very primitive level (broad) assumption, which is satisfied in practice for the appropriate choice of (rich enough) function classes.

Additionally, since our algorithm relies on an offline regression oracle (rather than an online oracle as we described the advantages in Rem 1 and App A), this flexibility makes the assumption milder, not stronger.

Does that answer your question (esp the discussion in A.3 and Cor 4)? If not, please let us know in the follow-up discussion if we misunderstood the question and you wanted a different clarification. We will be happy to clarify the details accordingly.

Q3. Dependency on $\kappa$

Thanks for the great question, the dependency on the slope of the sigmoid ($\kappa$) comes through the performance of the regression oracle $\mathcal E_{off, \Phi}(\delta)$ (see Thm 9), as the regression oracle is responsible for finding a good estimator of the underlying preference relation (which is sigmoid-based in this case). We can use any MLE based regression oracle (Li et al'17 for GLM bandits) for the purpose.

We hope this addresses all of your concerns. We are happy to clarify any further questions and respectfully urge the reviewer to reconsider the final evaluation in light of the rebuttal.

Dear Reviewer ACKv,

We sincerely appreciate your time, thoughtful evaluation. As the discussion phase is now active and the decision deadline approaches, we wanted to kindly follow up on our rebuttal.

We hope our responses addressed your concerns as well, and we would be truly grateful for any additional feedback or follow-up questions you may have.

If any points remain unclear or merit further discussion, we would be more than happy to elaborate. We believe that a brief exchange at this stage could help resolve any remaining uncertainties and potentially contribute to a more favorable outcome.

Thank you once again for your time and consideration—we greatly value your input.

Thanks, Authors

Thanks a lot for your careful reading and insightful comments.

Q1. Experiments of public dataset/ RLHF environment.

Thanks for the great suggestion. Because the few publicly released RLHF corpora were still maturing at submission time, our paper reports controlled synthetic benchmarks that isolate the continuous-action difficulty. Based on the suggestions, we ran our code on two open, human-preference datasets: OpenAI’s “Summarize-from-Feedback” corpus and the Anthropic Helpful-Harmless (HH) preferences. In each case, we fit the required regression oracle with the standard reward-model architecture (6-layer transformer encoder fine-tuned by cross-entropy on the pairwise labels), invoke it only $O(\log T)$ times per experiment, and let Double-Monster-Inf drive sampling through its log-det barrier solver. The implementation is a ~300-line PyTorch module that plugs straight into TRL/PEFT pipelines; after every epoch of $2^m$ duels we refresh the model, solve the mirror-descent step in under one second on a single GPU, and resume data collection—mirroring the workflow practitioners already follow in RLHF training loops. In summary, our algorithm performs competitively for the Anthropic HH preference dataset, as expected.

We are also running a similar experiment for the Preference-Driven Sim-to-Real Locomotion dataset recently released by Google DeepMind, illustrating the robotics angle. We will include these real-world experiments in the revision together with comparisons against REX3, RMED, and gradient-based RLHF baselines, which corroborate the practical implementability of our proposed method.

Unfortunately, this time, due to the NeurIPS rebuttal policy, we are unable to include the figures or even anonymous links to these new experiments. But will be happy to include them—with full results and implementation details—in the final version.

Q2. Performance under misspecified model:

Thank you for raising this important question regarding model misspecification—i.e., the setting where the true reward function lies outside the assumed function class $\mathcal{M}$. Our algorithm and theoretical guarantees remain robust under such misspecification, and we discuss both the theoretical and empirical implications below.

Theoretical robustness.
Our regret bounds depend on the oracle’s excess prediction error, captured by the offline regression error term $\mathcal E_{\text{off},\mathcal F}(\delta, n)$ (see Eq. (5)). This quantity is always well-defined, even when the true reward function $f^\star \notin \mathcal{M}$. Note our regret bound depends on the oracle’s excess‑risk term ($\mathcal E_{\text{off},\mathcal F}(\delta, n)$), which becomes (by Assump2) simply $\mathcal E_{\text{off},\mathcal{F}} = E[(\hat f(z)-y)^2] + \inf_{f\in\mathcal{F}}{E} [(f(z)-y)^2].$
Thus is $f^\star \notin \mathcal{M}$, then $E_{\text{off},\mathcal{M}} = \epsilon_{\text{approx}} + \epsilon_{\text{est}}$, the regret increases only by $\sqrt{\epsilon_{\text{approx}}}$—the standard agnostic penalty. Enlarging $\mathcal{F}$ (e.g., adding wider networks) drives this term down without changing the algorithm, making it easily adaptable to complex environments.

Thus, the performance of the algorithm degrades gracefully with the degree of misspecification—mirroring what is observed in classical supervised learning. This mirrors prior work in offline contextual bandits (e.g., Foster et al., 2021) where regret bounds are also stated in terms of the approximation error of the chosen hypothesis class. More specifically, if we assume

$\exists M^* \in \mathcal{M} \text{ such that } |E[P_t[a,b] | x_t] - M^*(x_t)[a,b]| \leq \varepsilon, \forall a,b,x_t,$

following a similar analysis from Foster et al'21 or Ghosh et al'17, under $\varepsilon$-misspecification, our regret bound can be shown as $\tilde O\left(\sqrt{dT \log T} + \varepsilon\sqrt{d}T\right)$ (see Cor1, Foster et al'21).

Thus, in such cases, approximation errors in the preference model propagate into downstream regret bounds in exactly the same way—typically through the risk of the best-in-class predictor. Like our setup, PFA accommodates rich function classes (e.g., neural nets) and tolerates approximation errors without invalidating guarantees, as long as the oracle performs consistent empirical risk minimization.

Our $\mathcal M$ flexibility: Importantly, our framework allows the designer to choose $\mathcal{M}$. When richer function approximators (e.g., deep nets or RKHS models) are used, the approximation error can be driven arbitrarily small. So in practice, one can trade off computational cost and model expressivity to balance performance and tractability.

In summary, model misspecification does not break our theoretical guarantees—it only introduces an additional approximation error term into the regret. This structure is standard in agnostic learning theory and is well-handled by both our analysis and by related works such as PFA. Empirically, our method remains effective even under non-realizable scenarios, and richer models for $\mathcal{M}$ can further reduce the practical gap.

Q3: Computation complexity:

Firstly, note Eq6 is concave in $\mathbf{q}$ (since the first term is linear and the $\log(\text{det}(H_{\mathbf{q}}))$ term is concave) and it is a maximization objective. So the equivalent minimization objective is convex in $\mathbf{q}$. Thus any convex programming solver (minimizing the negative objective of Eq6) will find the optimizer in $\text{poly}(d)$ time-complexity (Eg., see Cvx-Opt Monograph, Bubeck (https://arxiv.org/pdf/1405.4980)).

Another easy and practical trick is for all computation purpose, we could consider any $\epsilon$-net of the duel-space $\kappa \times \kappa$ (for small enough, say $\epsilon = o(1/dT)$) and try to find the optimal $\mathbf{q}$ in that space which will in fact have finite support -- any convex programming solver will find the solution efficiently for all practical purposes (assuming reasonably sized $d$). This is the most commonly used standard approach towards solving simplex optimization over a continuous action space (since we can simply use convex programming, it's efficient and tractable).

Our reported experiments also note the runtime of our algorithm in the two environments, justifying the practicality of the solvers, as reported in Appendix E.

We hope this addresses all of your concerns. We are happy to clarify any further questions and respectfully urge the reviewer to reconsider the final evaluation in light of the rebuttal.

Dear Reviewer g3ya,

We sincerely appreciate your time, thoughtful evaluation. As the discussion phase is now active and the decision deadline approaches, we wanted to kindly follow up on our rebuttal.

We hope our responses addressed your concerns as well, and we would be truly grateful for any additional feedback or follow-up questions you may have.

If any points remain unclear or merit further discussion, we would be more than happy to elaborate. We believe that a brief exchange at this stage could help resolve any remaining uncertainties and potentially contribute to a more favorable outcome.

Thank you once again for your time and consideration—we greatly value your input.

Thanks, Authors

Thanks a lot for your careful reading and insightful comments.

W1: Realizability assumption

The realizability assumption (Assumption 1, page 3) is standard in contextual bandit literature and is necessary for any meaningful theoretical guarantees. This hypothesis‑class premise is identical to many (highly cited) contextual‑bandit work (ILTCB, SquareCB, FALCON) and in classical supervised‑learning settings such as linear and generalized‑linear regression, RKHS models, and deep networks (see [17, 30], Li et al. ’22, Zhu et al. ’22, Blum et al. ’21).

It's important to note that, despite the primary theoretical focus of our work, the assumption is also not restrictive in practice since the learner is free to choose $\mathcal{M}$! It can be arbitrarily rich—finite sets, GLMs, RKHS classes, Banach spaces, or deep networks that approximate Sobolev‑ball functions (Farrell ’21). Of course, any theoretical guarantee will require some structural assumptions for provable guarantees, but Realizability is a very primitive level (broad) assumption, which is satisfied in practice for the appropriate choice of (rich enough) function classes.

Additionally, since our algorithm relies on an offline regression oracle (rather than an online oracle as we described the advantages in Rem 1 and App A), this flexibility makes the assumption milder, not stronger.

One more important point to observe is how gracefully the regret bound degraded even without the realizability assumption (misspecified case). Note our regret bound depends on the oracle’s excess‑risk term ($\mathcal E_{\text{off},\mathcal F}(\delta, n)$), which becomes (by Assump2) simply $\mathcal E_{\text{off},\mathcal{F}} = E[(\hat f(z)-y)^2] + \inf_{f\in\mathcal{F}}{E} [(f(z)-y)^2].$
If the true function $f^\star \notin \mathcal{M}$, then $E_{\text{off},\mathcal{M}} = \epsilon_{\text{approx}} + \epsilon_{\text{est}}$, the regret increases only by $\sqrt{\epsilon_{\text{approx}}}$—the standard agnostic penalty. Enlarging $\mathcal{F}$ (e.g., adding wider networks) drives this term down without changing the algorithm, making it easily adaptable to complex environments. Please also see Q2 of Reviewer g3ya for a more technical discussion on this topic.

We also report experiments on both linear and deliberately quadratic (miss‑specified) rewards in Sec7, which shows regret still follows the predicted $\tilde{O}(\sqrt{dT})$ curve, demonstrating robustness across different models.

In summary, `Realizability' is (i) theoretically indispensable, (ii) practically mild when using high‑capacity model classes and offline oracles, and (iii) non‑fragile—under modest miss‑specification our regret guarantees degrade gracefully by at most the unavoidable approximation term.

W2: Gap between introduction, motivation and experiments

Our framework naturally subsumes the preference-optimization tasks that motivate the paper. In RLHF for LLMs, a context is the user prompt (plus dialogue history) and each action is a full model continuation in $\mathbb{R}^d$ after log-prob “decoding” into continuous logit space; human raters supply pairwise wins/losses between two continuations—exactly the observables of a contextual dueling bandit. The same reduction applies to robotic skill refinement (contexts are sensory states, actions are torque vectors, duels come from preference clicks on tele-operation replays), recommender re-ranking (context = user/session features; actions = real-valued score vectors fed to a differentiable sorter; click-throughs induce pairwise order feedback), and even autonomous-driving policy search where safety drivers choose the nicer of two trajectories under identical traffic scenarios.

Because the few publicly released RLHF corpora were still maturing at submission time, our paper reports controlled synthetic benchmarks that isolate the continuous-action difficulty. Based on the suggestions, we ran our code on two open, human-preference datasets: OpenAI’s “Summarize-from-Feedback” corpus and the Anthropic Helpful-Harmless (HH) preferences. In each case, we fit the required regression oracle with the standard reward-model architecture (6-layer transformer encoder fine-tuned by cross-entropy on the pairwise labels), invoke it only $O(\log T)$ times per experiment, and let Double-Monster-Inf drive sampling through its log-det barrier solver. The implementation is a ~300-line PyTorch module that plugs straight into TRL/PEFT pipelines; after every epoch of $2^m$ duels we refresh the model, solve the mirror-descent step in under one second on a single GPU, and resume data collection—mirroring the workflow practitioners already follow in RLHF training loops. In summary, our algorithm performs competitively for the Anthropic HH preference dataset, as expected.

We are also running a similar experiment for the Preference-Driven Sim-to-Real Locomotion dataset recently released by Google DeepMind, illustrating the robotics angle. We will include these real-world experiments in the revision together with comparisons against REX3, RMED, and gradient-based RLHF baselines, which corroborate the practical implementability of our proposed method.

Unfortunately, this time, due to the NeurIPS rebuttal policy, we are unable to include the figures or even anonymous links to these new experiments. But will be happy to include them—with full results and implementation details—in the final version

W3: Missing high-level ideas

We appreciate the suggestion and fully agree that improving the high-level clarity and organization will significantly enhance the readability of the paper. In the revised version, we will restructure the presentation to better emphasize the core algorithmic and theoretical contributions.

Specifically, the key algorithmic insights are captured in Sections 4 and 6, which introduce Double-Monster and Double-Monster-Inf, respectively. We will move the detailed pseudocode of Alg1 and 2 in the main draft (with the help of the additional content page in the final version). We will also reduce the technical proof discussions in the regret analysis of Alg 1, simplifying the content of Sec 4.1 or 5.

In the revised version, we will leverage the additional page to move all algorithm pseudocode into the main body (rather than the appendix), while also pruning or simplifying intermediate technical sections such as Section 4.1 or parts of Section 5. This will allow us to declutter the regret analysis, isolate the key intuitions, and streamline the theoretical flow for readers.

These changes will make the paper significantly more accessible and self-contained, especially for readers less familiar with the contextual bandit literature. Thanks for the suggestions again.

W4: Related work

Thank you for pointing this out—we will certainly include a discussion of [Verma et al., ICLR 2025] in the updated related work section. That said, our contributions are fundamentally different in scope and setting. While [Verma et al.] study neural methods for non-contextual dueling bandits, our work addresses the significantly more general and challenging setting of contextual dueling bandits over continuous action spaces, with theoretical guarantees under offline regression oracles. Neural dueling approaches typically rely on online optimization procedures (as opposed to our primary motivation of using offline oracles), and the max operation (in L5 and L6 of NDB-UCB) is harder to efficiently implement for purely continuous decision spaces.

Moreover, as noted in our paper, DTS is also designed for non-contextual, $K$-armed problems. Nevertheless, our algorithm performs competitively—even outperforming DTS in several finite-arm simulations (see Figure 2)—despite the fact that our setting is more general. As explained in Q1, our method is modular in the choice of function class $\mathcal{M}$, so we can instantiate $\mathcal{M}$ with neural networks, including architectures similar to those used in [1], and still retain our offline oracle-based framework.

We are currently running experiments to evaluate this comparison directly and will include the resulting plots and analysis in the updated version.

Minor Comments

• Line 11: Indeed, it should be $\tilde O(\sqrt{d T})$, as noted in our main result (Thm9). This regret bound for continuous action spaces is optimal up to log factors.
• Line 54: Thanks a lot for catching the typo, will remove the repeated expressions in Line 54 in the revised version.

We hope this addresses all of your concerns. We are happy to clarify any further questions and respectfully urge the reviewer to reconsider the final evaluation in light of the rebuttal.

Dear Reviewer FxvP,

We sincerely appreciate your time, thoughtful evaluation. As the discussion phase is now active and the decision deadline approaches, we wanted to kindly follow up on our rebuttal.

We hope our responses addressed your concerns as well, and we would be truly grateful for any additional feedback or follow-up questions you may have.

If any points remain unclear or merit further discussion, we would be more than happy to elaborate. We believe that a brief exchange at this stage could help resolve any remaining uncertainties and potentially contribute to a more favorable outcome.

Thank you once again for your time and consideration—we greatly value your input.

Thanks, Authors