Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options

Thank you for your feedback and for engaging with our work.

The reviewer’s main concerns are (i) computational efficiency for large $K$ and (ii) the linear reward assumption. However, $K$ is typically small in practice (e.g., $K \leq 10$ in Ouyang et al., 2022), and the linear assumption is a standard and foundational choice in bandit and RL theory. Thus, these should not be viewed as weaknesses. We elaborate below.

Beyond the main concerns, we would like to reiterate the significance of our theoretical results:

1. the first theoretical result showing improved sample efficiency with multiple-option feedback (to our best knowledge),
2. the elimination of the exponential $e^B$ dependence common in prior PbRL—achieved without relying on any auxiliary techniques, such as self-sampling updates [1] or the use of $\kappa$-dependent weighted covariance matrix [2] ($\kappa$ is generally unknown in practice), and
3. The sample efficiency of RB loss and PL loss is equivalent in terms of the leading-order term. This result provides theoretical justification for the common empirical practice of decomposing ranking feedback into pairwise comparisons (Ouyang et al., 2022).
4. the first $K$-improving lower bound in PbRL.

For our first contribution, although it may seem intuitive that more options improve performance, no prior work has formally proven this—and most existing results actually degrade with larger $K$. Our result thus closes a long-standing gap between practical intuition and theory, marking a significant step forward for PbRL.

For our second contribution, removing the $e^B$ dependence is especially impactful, as many prior works failed to do so (e.g., Saha, 2021; Saha et al., 2023; Zhu et al., 2023; Xiong et al., 2023; Zhan et al., 2023). More importantly, the key lemmas used to eliminate the exponential $e^B$ dependence (Lemmas D.2 and E.1) are particularly significant, as they can be readily applied to many existing PbRL analyses without any modification to the underlying algorithms. This shows that the commonly observed $e^B$ dependence is not fundamental, but rather an artifact of loose analysis—an insight we find both surprising and broadly useful.

As we believe that all of your concerns have been thoroughly addressed and that our theoretical contributions are substantial, we respectfully ask the reviewer to reconsider the evaluation and recommend our paper for acceptance.

[1] Chen, Mingyu, et al. "Avoiding exp (rmax) scaling in rlhf through preference-based exploration." arXiv 2025.
[2] Di, Qiwei, Jiafan He, and Quanquan Gu. "Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback." ICML 2025.

• We Typically Consider Small $K$ Settings

The reviewer raised a concern about the large-$K$ scenario (i.e., when the maximum size of the assortment is large). However, in practice, small $K$ is typically used. For example, Ouyang et al. (2022) utilize ranking feedback of length 4 to 9.

Large-$K$ settings are generally unrealistic, as it is difficult to obtain accurate long rankings from human annotators. Therefore, we believe this concern should not be considered a weakness of our paper.

• Linear Model Is a Foundational Starting Point

Assuming linear rewards is a widely adopted approach for analyzing the statistical efficiency of PbRL, including dueling bandits. This modeling choice has been used in numerous prior works—such as Saha (2021), Wu and Sun (2023), Saha et al. (2023), Zhu et al. (2023), Di et al. (2024), Thekumparampil et al. (2024), among others—as a foundational tool for theoretical analysis.

Therefore, we strongly believe that this assumption should not be regarded as a unique weakness of our work, nor as a reason for rejection. The linear assumption serves as a fundamental starting point for understanding how the learning mechanism operates in PbRL. If certain phenomena fail to hold in this foundational setting, it is difficult to expect them to hold in more complex scenarios. Hence, we believe that the contributions outlined above are both meaningful and valuable to the community.

• Robustness to Model Misspecification in Experiments

Moreover, in our real-world experiment, there is indeed model misspecification: the features $\phi(x, a)$ and the true rewards come from different models. Specifically, the features $\phi(x, a)$ are extracted from the last hidden layer of Gemma-2B, while the true reward model is based on Mistral-7B. Despite this mismatch, our method still performs well, demonstrating a notable degree of robustness to model misspecification.

• Extension to General Function Approximation

To further address the reviewer’s concern about the linearity and PL model assumptions, we show that MAU (Maximizing Average Uncertainty) method can be extended to general function classes (i.e., general preference models), following a similar approach to Theorem 4 of Das et al. (2024). Specifically, given a function class $\mathcal{F}$, we define a confidence set

We then select the reference action-assortment pair $(\bar{a}\_t, S_t)$ according to:

Then, we can bound the suboptimality as:

where $d_{\mathcal{E},\mathcal{F}}$ and $\mathcal{N_\mathcal{F}}$ are the covering number and Eluder dimension of $\mathcal{F}$, respectively. The final inequality follows from Lemma 2 of [1], with minor modifications. Therefore, this result suggests that multiple-option feedback can lead to improved sample complexity for general function classes (including LLMs) as well.

We hope that this additional result can addresses the reviewer’s concern regarding the linear reward assumption and PL model assumption.

[1] Russo, Daniel, and Benjamin Van Roy. "Eluder dimension and the sample complexity of optimistic exploration." NeurIPS 2013.

• Q1. How do you decide between PL and RB losses?

Our theoretical results show that the suboptimality gaps of the PL and RB losses are comparable, especially as $T$ becomes large. While the RB loss may offer a slightly tighter non-leading term, this difference is negligible for large $T$. Therefore, both losses are statistically equivalent in the asymptotic regime.

However, the RB loss incurs higher computational cost due to the rank-breaking procedure. Therefore, we recommend using the PL loss when handling ranking feedback (just for its computational efficiency, not due to any statistical advantage).

• Q2. Did you consider comparing M-AUPO against such methods (e.g., PPO + BT model in [35] or DPO [38])?

The methods proposed in Ouyang et al. (2022) and Rafailov et al. (2023) operate purely in the offline setting—they optimize over a fixed dataset and do not make decisions about which actions to collect next. In contrast, M-AUPO is designed for the online setting, where the learner must actively select actions (or assortments) at each round. Therefore, a direct comparison would be methodologically inappropriate.

Instead, we compare against two baselines more relevant to the online RLHF setting:

• "Uniform", which selects actions uniformly at random (already included in Appendix I, and will be moved to the main paper in the revision), and
• "Best&Ref", which selects an action pair ($K=2$) using the current policy and a reference policy (e.g., uniform random or SFT), respectively—following a selection mechanism similar to those in Online GSHF [1] and XPO [2]..

We believe "Best&Ref" is the most appropriate baseline for online RLHF, as it closely mirrors how actions are selected in many existing online RLHF algorithms. Note again that DPO is best understood as an optimization algorithm for the offline setting, and thus not directly comparable in terms of online action selection or assortment design.

The results demonstrate that our method either consistantly and significantly outperforms all other baselines or is second-best with a minimal gap. (PL loss only, due to limited space.)

i) Synthetic experiment ($T=200$)

ii) Realworld experiment ($T=20,000$)

ii-1) TREC-DL dataset

ii-2) Nectar dataset

[1] Xiong, Wei, et al. "Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint." ICML 2024
[2] Xie, Tengyang, et al. "Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF." ICLR 2025

Please don’t hesitate to reach out if you have any further questions!

Dear Reviewer h2r7,

Thank you very much for your time and thoughtful evaluation of our work. As the discussion period comes to a close, we would like to kindly follow up on our rebuttal.

We hope that our responses have addressed your concerns. In particular, we respectfully ask that our use of linear models not be seen as a limitation. We believe that our theoretical contributions—the improved sample efficiency for longer ranking feedback and the elimination of $e^B$ dependence in the leading term (which also extends to existing PbRL and dueling bandits)—are substantial and merit acceptance.

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.

Best regards,
The Authors

We appreciate your time and thoughtful feedback in reviewing our paper.

Before addressing the reviewer's specific concerns, we would like to emphasize the importance of our theoretical contributions, which we believe are substantial but may have been somewhat underappreciated in your initial evaluation. Our key contributions and insights are as follows:

1. the first theoretical result showing improved sample efficiency with multiple-option feedback (to our best knowledge),
2. the elimination of the exponential $e^B$ dependence common in prior PbRL and dueling bandit literature—achieved without relying on any complex or auxiliary techniques, such as self-sampling updates [1] or the use of $\kappa$-dependent weighted covariance matrix [2] ($\kappa$ is generally unknown in practice), and
3. The sample efficiency of RB loss and PL loss is equivalent in terms of the leading-order term. This result provides theoretical justification for the common empirical practice of decomposing ranking feedback into pairwise comparisons, as done in works such as Ouyang et al. (2022).
4. the first $K$-improving lower bound in PbRL.

Especially, from a theoretical perspective, the key lemmas used to eliminate the exponential $e^B$ dependence (Lemmas D.2 and E.1) are particularly significant, as they can be readily applied to many existing PbRL analyses—provided elliptical potential lemmas are used—without any modification to the underlying algorithms. This demonstrates that the widely observed $e^B$ dependence was not a fundamental limitation, but rather an artifact of overly loose analysis. We believe this insight is both surprising and broadly useful.

Given the novelty, generality, and potential impact of our theoretical contributions, we kindly ask the reviewer to reconsider their evaluation and support our paper for acceptance.

[1] Chen, Mingyu, et al. "Avoiding exp (rmax) scaling in rlhf through preference-based exploration." arXiv (2025).
[2] Di, Qiwei, Jiafan He, and Quanquan Gu. "Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback." ICML 2025.

• First Rigorous Theoretical Justification of the Insight!

While it may appear intuitive that offering more options per round should improve performance (though it is unclear whether this is a widely recognized insight), no prior work has formally established this. In fact, most existing theoretical results worsen as $K$ increases, contradicting the intuition. Our result therefore closes a long-standing gap between intuition and theory, representing a meaningful step forward for the PbRL literature. We believe this contribution should be viewed as a strength—providing a complete theoretical justification of the intuition—rather than as a weakness.

Furthermore, we would like to clarify that—even though ranking feedback can potentially provide more data—it is not obvious whether this feedback contains sufficient information to yield meaningful information gain. For example, under the RB loss, if many item pairs are very similar in preference, the gain from such feedback is not guaranteed. Our paper explicitly addresses this issue by studying how to maximize the average uncertainty in the offered options, a challenge that we believe has not been adequately explored in prior work.

• Longer Options Are No Worse Than Shorter Options

We address your question comparing the following two settings:

• Option 1: $N$ questions with $M$ options each
• Option 2: $N/2$ questions with $2M$ options each

Our upper and lower bounds yield the following suboptimality ranges:

Option 1: $\Omega\left(\frac{d}{M\sqrt{N}}\right) \sim \tilde{\mathcal{O}}\left(\frac{d}{\sqrt{MN}}\right)$

Option 2: $\Omega\left(\frac{d}{2M\sqrt{N/2}}\right) \sim \tilde{\mathcal{O}}\left(\frac{d}{\sqrt{MN}}\right)$

These bounds suggest that the longer-option case (Option 2) is not worse than the shorter-option case (Option 1) in terms of sample efficiency. However, due to the remaining gap between the upper and lower bounds by a factor of $\sqrt{K}$ (i.e., the optimal rate is not yet identified), we cannot definitively say which option is always better. It is possible that Option 2 may be better, as its lower bound is strictly smaller. Alternatively, the two settings may be equivalent if the current upper bound is tight.

We believe that rigorously closing this gap is an interesting and important direction for future work, and we thank the reviewer for raising this constructive point. That said, even with the current bounds, we find the result valuable, as it suggests that either setting can be used depending on practical convenience, with comparable (or similar) statistical efficiency.

• Additional Experiments

In our experiments, we made every effort to include all relevant baselines and to cover a wide range of scenarios. We hope the reviewer finds our experimental evaluation sufficiently thorough.

1. vs. Other baselines
In Appendix I, we have already included an additional comparison with a "Uniform", which selects actions uniformly at random (to be moved to the main paper in the revision). To provide a more comprehensive evaluation, we now also include:

• "Uniform", which selects actions uniformly at random (already included in Appendix I, and will be moved to the main paper in the revision), and
• "Best&Ref", which selects an action pair ($K=2$) using the current policy and a reference policy (e.g., uniform random or SFT), respectively—following a selection mechanism similar to those in Online GSHF [1] and XPO [2].

We believe that "Best&Ref" is the most relevant baseline for online RLHF, as it reflects how many online RLHF algorithms select actions in practice. Note that a direct comparison with DPO is not appropriate, since DPO is best understood as an optimization algorithm for the offline setting, rather than an action (or assortment) selection strategy for the online setting.

The results demonstrate that our method either significantly outperforms all other baselines or is second-best with a minimal gap. (PL loss only, due to limited space.)

i) Synthetic experiment ($T=200$)

ii) Realworld experiment ($T=20,000$)

ii-1) TREC-DL dataset

ii-2) Nectar dataset

[1] Xiong, Wei, et al. "Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint." ICML 2024
[2] Xie, Tengyang, et al. "Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF." ICLR 2025

2. Varying values of $K$ is already included in Appendix I
A comparison between DopeWolfe and M-AUPO across varying values of $K$ is already included in Appendix I. Moreover, in the synthetic experiments, we evaluate our algorithm under diverse context structures. The results demonstrate the superior performance of our method across various settings. We also include runtime tables—covering both synthetic and real-world experiments—which highlight the computational efficiency of our algorithm. Please refer to Appendix I for further details.

• We Use Exact Theoretical Parameter Values in All Experiments

In all of our experiments, we used the exact same parameter values (e.g., $\lambda$, $\eta$, etc.) as defined in the theoretical results. For reference, please see the notation summary in Table C.1. Therefore, ablation studies on these parameters are unnecessary.

One key advantage of using theoretically grounded algorithms is that the prescribed parameter values can be directly applied in practice, without the need for exhaustive hyperparameter tuning. We will clarify this point more explicitly in the final version of the paper.

• (minor): As you pointed out, the denominator in Eq. (1) should indeed be $\sigma_k$. In fact, we had already made the correction in the supplementary appendix, but we still appreciate your attention to detail—thank you for pointing it out.

Please feel free to reach out if you have any further questions or require clarificationon any point!

Dear Reviewer fSmY,

We sincerely appreciate your time and thoughtful evaluation of our work. As the discussion period draws to a close, we would like to kindly follow up on our rebuttal.

We hope that our responses have addressed your concerns and that the significance of our theoretical contributions is recognized. If any aspects remain unclear or merit further discussion, we would be more than happy to provide additional clarification. We believe that a brief exchange at this stage could help resolve any outstanding uncertainties and contribute to a more informed final assessment.

We would also be truly grateful for any additional feedback or follow-up questions you may have.

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

Best regards,
The Authors

We appreciate the time you took to review our paper and your valuable feedback.

Before addressing the reviewer’s concerns, we would like to re-emphasize the significance of our theoretical contributions. Our primary contributions and interesting insights are:

1. the first theoretical result showing improved sample efficiency with multiple-option feedback (to our best knowledge),
2. the elimination of the exponential $e^B$ dependence common in prior PbRL and dueling bandit literature—achieved without relying on any complex or auxiliary techniques, such as self-sampling updates [1] or the use of $\kappa$-dependent weighted covariance matrix [2] ($\kappa$ is generally unknown in practice), and
3. The sample efficiency of RB loss and PL loss is equivalent in terms of the leading-order term. This result provides theoretical justification for the common empirical practice of decomposing ranking feedback into pairwise comparisons, as done in works such as Ouyang et al. (2022).
4. the first $K$-improving lower bound in PbRL.

From a theoretical perspective, the key lemmas used to eliminate the exponential $e^B$ dependence (Lemmas D.2 and E.1) are particularly significant, as they can be readily applied to many existing PbRL analyses—provided elliptical potential lemmas are used—without any modification to the underlying algorithms. This demonstrates that the widely observed $e^B$ dependence was not a fundamental limitation, but rather an artifact of overly loose analysis—an insight we find both surprising and highly impactful.

We believe these contributions mark a significant step forward in the theory of PbRL and are sufficient to merit acceptance. We also address all of the reviewer’s concerns below and hope the reviewer will reconsider our paper in light of these points.

[1] Chen, Mingyu, et al. "Avoiding exp (rmax) scaling in rlhf through preference-based exploration." arXiv (2025).
[2] Di, Qiwei, Jiafan He, and Quanquan Gu. "Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback." ICML 2025.

• Full Proofs Are Provided in the Appendix

We clarify that all theoretical proofs have already been provided in the appendix, which was submitted as part of the supplementary material in accordance with NeurIPS 2025 guidelines.

• Linear Model Is a Foundational Starting Point

Assuming linear rewards (with fixed features) is a widely adopted approach for analyzing the statistical efficiency of PbRL, including dueling bandits. This modeling choice has been used in numerous prior works—such as Saha (2021), Wu and Sun (2023), Saha et al. (2023), Zhu et al. (2023), Di et al. (2024), Thekumparampil et al. (2024), among others—as a foundational tool for theoretical analysis.

Therefore, we strongly believe that this assumption should not be regarded as a unique weakness of our work, nor as a reason for rejection. The linear assumption serves as a fundamental starting point for understanding how the learning mechanism operates in PbRL. If certain phenomena fail to hold in this foundational setting, it is difficult to expect them to hold in more complex scenarios. Hence, we believe that the contributions outlined above are both meaningful and valuable to the community.

• Extension to General Function Approximation

To further address the reviewer’s concern about the linearity and fixed feature assumptions, we show that MAU (Maximizing Average Uncertainty) method can be extended to general function classes, following a similar approach to Theorem 4 of Das et al. (2024). Specifically, given a function class $\mathcal{F}$, we define a confidence set $\mathcal{C}\_t(\mathcal{F}, \delta)$ and an exploration bonus:

We then select the reference action-assortment pair $(\bar{a}\_t, S_t)$ according to: $(\bar{a}\_t, S_t) := \arg\max\_{\bar{a}, S \,s.t.\, \bar{a} \in S} \frac{1}{|S|} \sum\_{a \in S} b_t(x, a, \bar{a}).$ Then, we can bound the suboptimality as:

where $d_{\mathcal{E},\mathcal{F}}$ and $\mathcal{N_\mathcal{F}}$ are the covering number and Eluder dimension of $\mathcal{F}$, respectively. The final inequality follows from Lemma 2 of [1], with minor modifications. Therefore, this result suggests that multiple-option feedback can lead to improved sample complexity for general function classes as well.

We hope that this additional result can addresses the reviewer’s concern regarding the linear reward assumption and the fixed feature assumption.

[1] Russo, Daniel, and Benjamin Van Roy. "Eluder dimension and the sample complexity of optimistic exploration." NeurIPS 2013.

• Our Bound Is a Clear Improvement

It seems there is a possibility that readers may misunderstand the prior bounds presented in Table 1. To clarify, we highlight two key points:

1. Prior works also incur $e^{4B}$ dependence: For example, Zhu et al. (2023), Mukherjee et al. (2024), and Thekumparampil et al. (2024) all include $\gamma = e^{-4B}$ (or $e^{-4}$ when $B = 1$), implying an $e^{4B}$ dependence. Thus, the second term in our bound is NOT weaker than theirs.
2. The Sq. Pred. Error measure used in Mukherjee et al. (2024) and Thekumparampil et al. (2024), roughly speaking, corresponds to the square of our suboptimality.: Taking square roots, their bounds become $\tilde{\mathcal{O}}\left(\frac{d K^3}{\kappa \sqrt{T}}\right)$—which is worse than ours $\tilde{\mathcal{O}}\left(\frac{d}{T} \sqrt{\sum_{t=1}^T \frac{1}{|S_t|}} + \frac{d^2}{\kappa T}\right)$ in terms of both $K$ and $\kappa$.

Therefore, our bound is a strict improvement, and even the second term alone is NOT weaker than existing results for large $B$. We will make this clarification more explicit in the revised version. Thank you for pointing this out.

• Additional Experiments

1. vs. Other Baselines

In Appendix I, we have already included an additional comparison with a "Uniform", which selects actions uniformly at random (to be moved to the main paper in the revision). To provide a more comprehensive evaluation, we now also include:

• "Uniform", which selects actions uniformly at random (already included in Appendix I), and
• "Best&Ref", which selects an action pair ($K=2$) using the current policy and a reference policy (e.g., uniform random or SFT), respectively—following a selection mechanism similar to those in Online GSHF [1] and XPO [2].

The results demonstrate that our method either significantly outperforms all other baselines or is second-best with a minimal gap. (PL loss only, due to limited space.)

i) Synthetic experiment ($T=200$)

ii) Realworld experiment ($T=20,000$)

ii-1) TREC-DL dataset

ii-2) Nectar dataset

The reviewer also suggested comparing sub-optimality gaps with the methods in Table 1. However, Zhu et al. (2023) and Mukherjee et al. (2024) assume fixed (given) assortments, a different and simpler setting that does not account for interactive decision-making—crucial in real-world tasks like web search, where only the top-ranked results can be labeled. Therefore, a direct comparison with these methods is either infeasible or inappropriate.

[1] Xiong, Wei, et al. "Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint." ICML 2024
[2] Xie, Tengyang, et al. "Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF." ICLR 2025

2. Robustness to Varying B

In response to the reviewer’s request, we report suboptimality across varying values of $B$ in our synthetic experiments. As shown below, our algorithm is quite robust to the scale of $B$ in practice, e.g., $(K=2, B=1) \approx (K=5, B=10)$.

i) $K=2$

ii) $K=5$

Q. What the norms of the features look like in the real-world setting?

In our real-world experiments, we use the reward from Mistral-7B as the true reward signal, which ranges from approximately –20 to 20. Since we assume $\\|\phi(x,a)\\|_2 \leq 1$, this implies that the norm bound on $\theta$ (i.e., $B$) is approximately on the order of 20.

We welcome any additional questions!

We sincerely thank you for taking the time to carefully read our lengthy rebuttal. We're very glad to hear that you recognized the significance of our theoretical contributions and chose to update your score. (While we cannot yet see the updated score, we truly appreciate your support for our work!)

We’re very glad to have addressed your remaining concerns.

Maximizing Average Uncertainty Beyond Linear Model

Thank you for raising this point. We now understand that your concern pertains to the practicality of our method for selecting assortments (i.e., sets of actions) in settings beyond the linear model.

One promising direction is to leverage the neural tangent kernel (NTK) framework [1]. Specifically, following the neural contextual bandit literature [2,3] and recent advances in neural dueling bandits [4], we can estimate the uncertainty between actions $a$ and $a'$ given context $x_t$ as:

where $g(x_t, a ; \theta_t)$ denotes the gradient of the neural network output with respect to its parameters $\theta_t$, and $H_t$ is a regularized Fisher or NTK Gram matrix.

We can then select the reference-assortment pair $(\bar{a}\_t, S_t)$ as follows:

Note that this is a high-level idea, and formalizing it would involve several technical challenges. That said, if this method is feasible, one particularly appealing aspect is that our method may eliminate the need for a confidence radius term $\beta_t(\delta)$—and consequently, it would NOT require knowledge of the effective dimension $\tilde{d}$, which is typically difficult to estimate in practice. This highlights the potential practicality of our approach based on maximizing average uncertainty.

We believe this is a very promising and important direction for future research. We plan to include a clearer discussion of this idea, along with its current limitations, in our revision. Thank you again for your insightful and constructive feedback—it will undoubtedly help advance the field!

On the other hand, we would like to emphasize that all existing methods in PbRL also come with their own practical limitations. For example, XPO (Xie et al., 2025), though relatively easy to implement, requires knowledge of the coverability coefficient $C_{\text{cov}}(\Pi)$—a quantity that is typically unknown in practice. (In contrast, our method does not require access to the complexity measure $\tilde{d}$.) Moreover, Online GSHF (Xiong et al., 2024) provides theoretical guarantees only under linear reward assumptions (as we do), but employs a heuristic method in experiments that has no theoretical justification.

Thus, limited practicality is not a unique drawback of our approach, but rather a prevalent challenge across PbRL theory. In particular, quantifying uncertainty beyond the linear model remains a long-standing and open problem, and addressing it is crucial for advancing the field.

[1] Jacot, Arthur, Franck Gabriel, and Clément Hongler. "Neural tangent kernel: Convergence and generalization in neural networks." Advances in neural information processing systems 31 (2018).
[2] Zhou, Dongruo, Lihong Li, and Quanquan Gu. "Neural contextual bandits with ucb-based exploration." International conference on machine learning. PMLR, 2020.
[3] Zhang, Weitong, et al. "Neural Thompson Sampling." International Conference on Learning Representation (ICLR). 2021.
[4] Verma, Arun, et al. "Neural Dueling Bandits: Preference-Based Optimization with Human Feedback." The Thirteenth International Conference on Learning Representations.

Dependency on $e^B$ in Lower-order Term

First, we would like to correct your minor typo: the lower-order term in our bound is $\tilde{\mathcal{O}}(e^{4B} d^2 / T)$, not $\tilde{\mathcal{O}}(e^{8B} d^2 / T)$.

As you noted, when $B$ is very large and $T$ is small, this term can dominate and lead to large suboptimality gaps. However, we emphasize the following:

• The exponential dependence on $B$ in the lower-order term is not unique to our work. It appears in nearly all related literature—including logistic bandits (Faury et al., 2020; 2022; Abeille et al., 2021), GLM bandits (Lee et al., 2024; Sawarni et al., 2024), MNL bandits (Zhang and Sugiyama, 2024; Lee and Oh, 2024), and dueling bandits (Di et al., 2025; Chen et al., 2025). This dependence is widely acknowledged as unavoidable, due to the intrinsic non-linearity of sigmoid and softmax functions.

Thank you very much for your positive review! Below, we provide our responses to your comments and concerns.

• The Parameter Boundedness $B$ Is Typically Large in Practice

We respectfully disagree with the claim that $B$ is generally a small constant. In many real-world scenarios, $B$ can in fact be quite large. For example, in our real-world experiments, the reward function derived from Mistral-7B spans a range of approximately –20 to 20. Given that we assume $\\|\phi(x,a)\\|_2 \leq 1$, this implies that the norm bound on $\theta$, i.e., $B$, must also scale with 20. Therefore, we strongly believe that eliminating exponential dependence on $B$ (e.g., $e^B$) represents a substantial and meaningful improvement.

In many prior works on logistic bandits (Faury et al., 2020; 2022; Abeille et al., 2021), GLM bandits (Lee et al., 2024; Sawarni et al., 2024 [1]), and MNL bandits (Zhang and Sugiyama, 2024; Lee and Oh, 2024), eliminating or reducing the $e^B$ dependence has been recognized as a central research goal. In contrast, PbRL and dueling bandit literature (e.g., Saha, 2021; Saha et al., 2023; Zhu et al., 2023; Xiong et al., 2023; Zhan et al., 2023) has largely overlooked this issue, and whether $e^B$ dependence can be avoided has remained a long-standing open question.

In this paper, we show that it is indeed possible to eliminate the $e^B$ dependence without relying on auxiliary techniques, such as specialized sampling schemes [2] or prior knowledge of $\kappa$ [3], which are often impractical. Our improvement is enabled by rethinking the Hessian as a conditional expectation of the covariance matrix and applying matrix concentration inequalities repeatedly (see Lemmas D.2 and E.1).

This proof technique is not only theoretically elegant but also broadly applicable: it can be directly applied to any existing PbRL or dueling bandit analysis, including regret-minimization settings, as long as elliptical potential lemmas are used—without modifying the original algorithm! This reveals that the exponential dependence on $B$ was not fundamentally necessary, but rather a byproduct of loose analysis.

We strongly believe this new perspective deepens the theoretical understanding of PbRL and dueling bandits, and could inspire new research directions in the field.

[1] Sawarni, Ayush, et al. "Generalized linear bandits with limited adaptivity." Advances in Neural Information Processing Systems 37 (2024): 8329-8369.
[2] Chen, Mingyu, et al. "Avoiding exp (rmax) scaling in rlhf through preference-based exploration." arXiv (2025).
[3] Di, Qiwei, Jiafan He, and Quanquan Gu. "Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback." ICML 2025.

• Efficient $\mathcal{O}(NK)$ Assortment Selection Provided in Appendix

In Appendix H.1, we introduce a more efficient assortment selection strategy. Instead of selecting the reference action $\bar{a}_t$ that maximizes the average uncertainty, we simply choose $\bar{a}_t \in \mathcal{A}$ arbitrarily. We show that this simplification still yields the same theoretical guarantees while reducing the computational cost to $\mathcal{O}(NK)$. We believe this is a significant improvement, as prior works in the dueling bandit literature typically incur $\mathcal{O}(N^2)$ computational costs (e.g., Saha, 2021; Bengs et al., 2022), which is worse than ours since $K \ll N$ in general.

• Saha (2021) and Bengs et al. (2022) Assume Stronger Context Conditions

We would like to clarify that both Saha, 2021 and Bengs et al., 2022 make stronger assumptions on the context (feature) vectors. Specifically:

1. Saha (2021) assumes that the feature vectors at each round $t$ are drawn i.i.d. from a fixed distribution.
2. Bengs et al. (2022) imposes a more stringent condition (Assumption A1), requiring that the offered feature vectors contain a set of basis vectors satisfying $\rho \mathbf{I}\_d \leq \sum\_{j=1}^d b_j b_j^\top,$ for some constant $\rho>0$.

In contrast, we do not require any structural assumptions on the feature vectors $\phi(x,a)$; they can be specified arbitrarily. Even though we assume a fixed context distribution and a stationary action space in our main presentation for simplicity, our analysis readily extends to settings where both the context distribution and the action space vary over time (and can be given arbitrarily). We will make this point more explicit in the revised version, in addition to the brief note already provided in Footnote 1.

Therefore, we strongly believe that comparisons to their algorithms and results are not meaningful, as they rely on significantly stronger assumptions. In particular, without these contextual assumptions, their algorithms and analyses break down entirely and cannot achieve the regret bound of $\mathcal{O}(\sqrt{dT \log N} )$ in more general setting we consider.

• Q1. Is there an inherent difficulty in this work to provide a regret analysis?

No, there is no inherent difficulty. In fact, our method readily admits a regret analysis. Specifically, define the greedy policy at round $t$ as $\hat{\pi}\_t(x) = \arg\max\_{a \in \mathcal{A}} \phi(x, a)^\top \hat{\theta}\_t$. Then, following the similar analysis as in the proof of Theorem 1 (and ignoring non-leading terms for simple presentation), we obtain:

This result also shows that the regret improves with larger comparison sets $S_t$, clearly demonstrating the benefit of multiple-option feedback. We appreciate the constructive question.

• Q2. Comparison to the lower bound of Saha (2021). How can the difference be explained?

First, we would like to emphasize that there are fundamental differences in the problem setting. Saha (2021) considers one-click feedback among the $|S_t|$ items, whereas our setting assumes access to the full ranking feedback over $|S_t|$ items. Hence, our setup reflects a richer information setting, which naturally allows for improved statistical efficiency—especially in terms of dependence on $K$.

Moreover, the definitions of regret differ. In Saha (2021), the regret is defined as an average reward gap:

whereas in our case, the suboptimality gap is defined as the gap between the optimal and the current best item (for simplicity, let $x \leftarrow \phi(\cdot, \cdot)$):

Due to these key differences in feedback type and regret formulation, a direct comparison to the lower bound in Saha (2021) is not appropriate. That said, if one were to hypothetically align the performance measures and consider the special case of $K = 2$, then our lower bound of $\Omega\left(\frac{d}{\sqrt{T}}\right)$ is strictly tighter than theirs, which is $\Omega\left(\sqrt{\frac{d}{T}}\right)$. (We also note that their bound does not include any dependence on $\log N$.)

To directly address your question on why the bounds differ, we cautiously suggest that the looser bound in Saha (2021) arises from the choice of instance construction. A similar phenomenon can be observed in Theorem 3.1 of Bengs et al. (2022), where the authors derive an $\Omega(d \sqrt{T})$ lower bound under the assumption that $\theta^\star \in \mathcal{B}_1(2)$ and $\mathcal{X} \subseteq \mathcal{B}_1(\infty)$, but only an $\Omega(\sqrt{dT})$ bound when $\mathcal{X} \subseteq \mathcal{B}_1(2)$.

We speculate that a comparable $\Omega\left(\sqrt{\frac{d}{T}}\right)$ suboptimality gap could also be derived in our setting by constructing a different (weaker) instance. However, since this would yield a looser bound than our current result, we do not explore this direction further in the this rebuttal.

Please feel free to reach out if you have any further questions!

Thank you for your quick response and for taking the time to read through our previous, albeit lengthy, rebuttal.

However, we believe that some confusion may have arisen due to notational differences across the papers. Specifically, in Saha (2021) and Bengs et al. (2022), the $K$ denotes the total number of arms. In contrast, in our paper, $K$ refers to the maximum size of the offered item set, while $N$ denotes the total number of arms. When $K = 2$ in our setting (i.e., the pairwise comparison case), our problem reduces to theirs.

To enable a fair comparison of the regret bounds, we restate them below for the case of $K = 2$:

• Saha (2021), Bengs et al. (2022): $\mathcal{O}(\sqrt{dT \log N})$, where $N$ is the total number of arms.
• Ours: $\mathcal{O}(d\sqrt{ T } )$, again when $K = |S_t| = 2$ (i.e., the pairwise comparison setting).

Notably, our bound does NO depend on $N$, the total number of arms. Even in extreme cases where the number of arms is exponential in dimension (e.g., $N = 2^d$), our regret remains unchanged.

Furthermore, we re-emphasize that our analysis holds in the more general adversarial feature setting, whereas the results of Saha (2021) and Bengs et al. (2022) crucially rely on i.i.d. stochastic features or strong basis vector assumptions. Their analyses do not extend to the adversarial setting we consider and, in fact, would fail entirely under such conditions.

To the best of our knowledge, no prior work provides a regret bound that is strictly better than ours in this adversarial setting when $K = 2$. Moreover, for $K > 2$, our derived regret bound of $\mathcal{O}\left(d \log K\sqrt{ \sum_{t=1}^T \frac{1}{|S_t|} } \right)$ is the tightest known to date!

Please don’t hesitate to reach out if any questions remain—we would be more than happy to clarify further. Otherwise, if our responses have fully addressed the reviewer’s concerns, we would respectfully and sincerely appreciate any consideration to strengthen the evaluation in light of these key clarifications and contributions.

We sincerely appreciate your consistent support for our paper and your thoughtful, constructive feedback! In particular, we will take care to clearly explain how our setting differs from that of Saha (2021) and Bengs et al. (2022), and provide a more explicit comparison to their results. Once again, thank you for your valuable time and for serving as a reviewer.