- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper studies realizable contextual dueling bandits under the Bradley–Terry–Luce model with bounded latent rewards. It proposes SI-CDB, combining a log-loss confidence set, a greedy target arm, and an optimistic comparator. The asymmetric selection rule bounds two-arm regret through estimation errors on the queried pair, enabling a localized excess-loss analysis. The general-class guarantee is expressed through covering numbers and localized eluder dimensions. For linear rewards, the leading term is , while an additive term retains exponential dependence on . Validation consists of theoretical proofs; no experimental or application study is provided, and the guarantees assume exact optimization.
Critical strengths
-
The asymmetric comparator objective bounds regret using estimation errors on the queried pair, providing a useful bridge from preference prediction to two-arm latent-reward regret.
-
For linear rewards, the leading regret term improves the explicit reward-scale dependence while preserving optimal dimension and horizon dependence, providing a concrete theoretical advance.
Critical weaknesses
-
The practical significance of the improvement is unvalidated. There are no experiments, application studies, or ablations. This matters because Corollary 5.5 retains an additive term proportional to , which can dominate the bound at finite horizons. Consequently, the paper does not establish whether the proposed comparator improves query efficiency over existing methods at realistic budgets. Appendix G describes approximate optimization procedures, but provides neither empirical evaluation nor guarantees for their approximation errors.
-
The benefit beyond linear reward classes is insufficiently substantiated. The general theorem depends on localized eluder dimensions and metric entropy, but the paper explicitly bounds these quantities only for linear rewards. It therefore remains unclear which representative nonlinear classes enjoy the claimed favorable reward-scale dependence. In particular, removing an explicit inverse-curvature factor does not by itself exclude such dependence through the complexity measures. This limits the demonstrated significance of the paper’s central general-function-approximation claim.
Questions for authors
-
Can the concentration and counting arguments be corrected explicitly? In Appendix C.1, Lemma E.1 requires a bound on , but the proof takes . For , , and , this centered quantity equals ; appears appropriate. Please also reconcile the historical budget with (B.5), and the disappearing factor of two before (B.8). Please provide a consistent confidence radius and corrected argument establishing the stated rates.
-
Under what conditions does the general-class theorem imply the claimed saturation-insensitive dependence? The leading term contains , and the nonlocalized contribution depends on . Which conditions ensure that these quantities do not introduce exponential dependence on , or stronger-than-logarithmic dependence on ? A representative nonlinear class with explicit complexity bounds would materially strengthen my assessment.
-
Could the incremental contribution relative to the closest work be stated more precisely? Which ingredients beyond the asymmetric regret decomposition are new relative to Bakhtiari et al.’s localized-eluder analysis and existing local-curvature dueling methods? Please also make Section 2 consistent with Appendix F.1 regarding Chen et al.: SE-POPO provides final-policy latent-reward guarantees and a general-function extension, so the distinction should be stated in terms of the learning objective and guarantee, rather than suggesting that the prior work only controls preference regret.
-
Could the authors provide a controlled synthetic comparison across reward scales and time horizons against a curvature-aware dueling baseline and an ablation of the comparator rule? Reporting cumulative two-arm regret, the distribution of queried gaps or link curvatures, and computational cost would help determine whether the asymptotic improvement translates into a practical advantage. Evaluating the approximate implementation from Appendix G would also clarify how much the result depends on exact optimization.
5 comments
Response to Reviewer Tm6w
Q3. The benefit beyond linear reward classes is insufficiently substantiated. The general theorem depends on localized eluder dimensions and metric entropy, but the paper explicitly bounds these quantities only for linear rewards. It therefore remains unclear which representative nonlinear classes enjoy the claimed favorable reward-scale dependence. In particular, removing an explicit inverse-curvature factor does not by itself exclude such dependence through the complexity measures.
A3. Thank you for this question. Theorem 5.3 yields a saturation-insensitive guarantee whenever the following two conditions hold:
- grows polynomially in and logarithmically in . This holds, for example, for any class parameterized by a bounded -dimensional parameter with a Lipschitz parameterization.
- The localized eluder dimension at scale grows polynomially in and polylogarithmically in . The quantity enters only the -independent additive term.
To make the second condition concrete, we have added Appendix D.2 on generalized linear rewards with polynomial link of degree , which need not be monotone. Lemma D.7 shows that the second condition holds for any convex class that is linear in some (possibly lifted) feature map, and Lemma D.6 shows that the localized eluder dimension is monotone in the class. Together, they give explicit bounds for representative nonlinear classes:
- Complexity bounds. (Proposition D.5) and with (Proposition D.8). Neither bound introduces exponential dependence on or more than logarithmic dependence on .
- Regret. Corollary D.9 gives a leading term . For the quadratic link (Example D.10), this is .
- Further examples. Two-layer networks with quadratic activation and arbitrary width (Example D.11) and a contextual ideal-point preference model (Example D.12).
Appendix D.2 also notes that the refined analysis of Appendix E improves the leading term to .
Q4. Can the concentration and counting arguments be corrected explicitly? In Appendix C.1, Lemma E.1 requires a bound on , but the proof takes . For , , and , this centered quantity equals ; appears appropriate. Please also reconcile the historical budget with (B.5), and the disappearing factor of two before (B.8). Please provide a consistent confidence radius and corrected argument establishing the stated rates.
A4. Thank you for checking the proof so carefully. All three points are correct. Each affects only numerical constants, and the stated rates are unchanged. We have made the following corrections in the revised manuscript (highlighted in blue).
- Range parameter in Lemma E.1 (Now Lemma F.1). Condition 1 of Lemma F.1 concerns the centered quantity . Lemma B.5 gives , so the correct choice is , together with from Lemma C.1. The confidence radius becomes in place of . Its order, , is unchanged. We have also added the one-line derivation of to the proof of Lemma B.5.
- Historical budget in (B.5). Lemma B.4 bounds the historical excess loss by , and this is the budget that enters Lemma F.2. The corrected (B.5), which also fixes the typo on the left-hand side, reads so .
- Factor of two before (B.8). We have . With , this gives .
With these corrections, Theorem 5.3 reads with and as above. The statement of Theorem 5.3 and Appendices B–C have been updated accordingly.
Response to Reviewer Tm6w
Q5. Could the incremental contribution relative to the closest work be stated more precisely? Which ingredients beyond the asymmetric regret decomposition are new relative to the localized-eluder analysis of [2] and existing local-curvature dueling methods [3]?
A5. Thank you for the question. We will add a paragraph to Section 6 that separates the imported tools from the new steps.
Relative to [2]. We import their uniform concentration (Lemma F.1), variance bound (Lemma C.1), localized-eluder counting lemma (Lemma F.2), and the witness rescaling behind Prop. D.2. Their regret-to-loss bridge does not transfer to dueling bandits, for two reasons:
- The learner observes only the queried reward difference, while the regret involves the unqueried optimal action.
- Regret is measured in latent rewards, so converting excess log loss into a reward-gap error costs at the queried gap, which can be .
Beyond the decomposition (Lemma B.2), the new ingredients are:
-
Query-gap localization from two-armed regret. Since penalizes both queried actions, . On rounds where both errors are at most , all queried gaps are therefore at most . Lemma B.3 then gives the two-sided bound :
- the left inequality converts loss into regret with local, rather than worst-case, curvature;
- the right inequality places the losses at the scale where the localized eluder dimension is evaluated.
This localization takes place in query space and is produced by the comparator choice. Single-action bandits have no analogue, and it is the reason single-arm regret alone would not suffice.
-
Two coupled estimators. The two errors come from different model sequences, the MLE and the optimistic model. We show that both have historical excess loss at most (Lemma B.4), so the localized counting applies to each. This is done at scale on localized rounds and at scale when counting the remaining rounds.
Relative to local-curvature dueling methods (RCDB-S [3]). These methods are specific to linear rewards. They estimate local link derivatives to build a derivative-weighted covariance matrix and rely on elliptical-potential arguments; for sigmoid feedback they obtain a leading term . Our analysis uses no covariance matrix and applies to general reward classes through the localized eluder dimension of the excess-loss class. Specialized to linear rewards, it gives the leading term , which improves the -dependence from to . With the refined analysis of the new Appendix E, the leading term further improves to (Corollary E.3).
Q6. Please make Section 2 consistent with Appendix F.1 regarding [4]: SE-POPO provides final-policy latent-reward guarantees and a general-function extension, so the distinction should be stated in terms of the learning objective and guarantee, rather than suggesting that the prior work only controls preference regret.
A6. Thank you. As you note, SE-POPO uses preference-based regret as an intermediate tool and ultimately provides latent-reward guarantees for the final policy, with polynomial dependence on the reward scale and an extension to general function classes. The distinction lies in the learning objective. [4] bound the suboptimality of the learned policy. We bound the cumulative two-armed latent-reward regret of an online learner, in which both queried actions are penalized at every round, so exploratory comparisons themselves incur regret. We have replaced the sentence in Section 2 with:
[4] avoid exponential reward-scale dependence in online RLHF through preference-based exploration with an iteratively updated sampler. They obtain final-policy latent-reward guarantees with polynomial dependence on the reward scale, including for general function classes. Their objective is the suboptimality of the learned policy, whereas we study cumulative two-armed reward regret, in which both queried actions incur regret at every round. For this online objective, removing the exponential dependence from the leading regret term for general reward classes has remained open.
We have also aligned the wording of Appendix F.1 (now G.1) with this description. Both changes are highlighted in blue.
References
[1] Verma et al. Neural Dueling Bandits: Preference-Based Optimization with Human Feedback. 2025
[2] Alireza Bakhtiari, Alex Ayoub, Samuel Robertson, David Janz, and Csaba Szepesvári. Eluder dimension: Localise it! 2026.
[3] Qiwei Di, Jiafan He, and Quanquan Gu. Nearly optimal algorithms for contextual dueling bandits from adversarial feedback. 2025.
[4] Mingyu Chen, Yiding Chen, Wen Sun, and Xuezhou Zhang. Avoiding exp(R) scaling in RLHF through preference-based exploration. 2025
Response to Reviewer Tm6w
Q1: No experiments; please compare across reward scales and horizons with a baseline and a comparator ablation, reporting two-arm regret, queried link curvatures and computational cost.
A1: We have added these experiments in Appendix H of the revision.
Setup. We evaluate a contextual dueling bandit with nonlinear rewards rθ(x,a)=Btanh(x⊤Wa+∑jqjaj2) over a continuous action space for B∈{0.5,1,2,4} (1/σ′(2B)∈[5,3×103]), T=5000 rounds, and 5 seeds. Since most existing contextual dueling bandit algorithms are restricted to linear rewards, we adopt the neural dueling bandit algorithms NDB-UCB and NDB-TS as baselines [1].
Cumulative two-arm regret at T=5000 (mean ± 95% CI).
The regret of SI-CDB remains stable across B and grows sublinearly in T for every B (Figure 2), showing that the additive 1/σ′(2B)-dependent lower-order term does not dominate at this horizon. SI-CDB achieves the lowest regret across all B, with a particularly large margin at B=4.
Queried link curvatures. For SI-CDB, fewer than 1% of the queried pairs have σ′(Δr⋆)<0.2 at every B, so its queries stay away from saturation even at B=4. The baselines behave similarly for B≤1, but at B=4, 67% (NDB-UCB) and 50% (NDB-TS) of their queries have σ′(Δr∗)<0.1.
Computation: See A2.
Q2. Appendix G describes approximate optimization procedures, but provides neither empirical evaluation nor guarantees for their approximation errors. Evaluating the approximate implementation from Appendix G would clarify how much the result depends on exact optimization.
A2:
All our experiments use the approximate implementation (now Appendix H.1). We add an ablation that varies the accuracy of each approximation separately (Appendix H.4, Table 4), in the same setting (B∈{0.5,1,2,4}, T=5000, 5 seeds). For the reward-model update, we change the number of Adam steps per round from 8 to 2 and to 32. For the comparator problem, we change the number of (restarts, outer rounds) of the alternating procedure from (3, 8) to (1, 2) and to (6, 16). The table reports the cumulative two-arm regret (mean ± 95% confidence half-width) and the time per round on a single CPU core.
For every B, the differences between the rows are within the variation across seeds, and a more accurate reward-model update or comparator search does not improve the regret systematically. The regret remains insensitive to B at every level of accuracy.
Although we do not have a guarantee for the approximation error and our theory assumes exact optimization, the ablation indicates that the empirical behavior does not rely on solving the two problems accurately.