Neural Dueling Bandits: Preference-Based Optimization with Human Feedback

We would like to thank the reviewer for taking the time to review our paper. We also thank the reviewer for acknowledging that our results are significant contributions to bandits. We have addressed each of the weaknesses and answer your questions as follows:

L59-63: Could you be more specific?

In previous work, Saha (2021) and (Li et al., 2024) select the most informative pair of arms, while Bengs et al. (2022) select the first arm optimistically and select the second arm that beats the first arm optimistically. In contrast, our proposed algorithms select the first arm greedily to ensure the best-performing arm is always selected and then the second arm optimistically to focus on exploration. This strategy makes our arm-selection process computationally efficient as our algorithms only need to compare $(K-1)$ pairs instead of all possible pairs (i.e., $O(K^2)$). Additionally, since we use an NN-based reward estimator, our optimistic term calculations for the context-arm pairs differ from the existing algorithms. As a result, our regret analysis uses novel techniques different from existing algorithms for contextual dueling bandits. We have added this discussion in Appendix C.2 and a reference to this discussion in the introduction of our revised paper.

L85-94: Since many readers may be unfamiliar with dual bandits, the description should be more detailed. For instance, the authors should clarify that the learner selects two arms from the action set with multiple arms, plays both arms, and receives feedback from both, which is captured as the preference y_t. It would be helpful to emphasize how this differs from standard contextual bandits.

We appreciate your suggestion to clarify the difference between contextual dueling bandits and standard contextual bandits. In the contextual dueling bandits problem, the learner selects two arms for a given context and observes comparative preference feedback over selected arms, indicating which arm was preferred. This problem differs from standard contextual bandits in which a learner selects a single arm and observes an absolute numerical reward for that arm. To clarify the difference, we added this discussion in the revised paper to highlight the difference between contextual dueling bandits and standard continual bandits.

Additionally, the authors introduce the context-arm set X_t. As the reviewer understands, this is no different from setups where either an action or context set is considered as long as a context and action pair is in R^d. Is there any technical distinction between the two? If not, this setup seems to introduce unnecessary complexity.

Your understanding is correct. The set $X_t$ represents all the context-arm feature vectors in round $t$. While it is equivalent to setups where context-arm pairs are considered separately, our motivation for introducing this notation is to simplify and unify our mathematical representation. By grouping context and arm space into a single notation $X_t$, we avoid using separate notations for context and action spaces. Using $X_t$ helps simplify the presentation and makes the paper's notation cleaner and more concise. We hope this clarifies the reasoning behind our choice of notation.

L95-111: The authors stated that the logistic function is considered as the link function, but stated in Assumption 1 that a class of link functions satisfying two conditions is considered in this work. For the reviewer, this description is confusing.

Our theoretical results are not limited to the BTL (Bradley-Terry-Luce) model but also hold for other preference models, such as the Thurstone-Mosteller model and Exponential Noise, as long as the stochastic transitivity property holds (Bengs et al., 2022). To generalize our results across different preference models, we need to make standard assumptions on the function $\mu$. The function $\mu$ is also referred to as a link function in the literature (Li et al., 2017; Bengs et al., 2022). The value of $\kappa_\mu$ and $L_\mu$ for the link function depends on the context space and preference model, e.g., $L_\mu \le 0.25$ for the BTL model.

L112-120: As these regrets are not common in other literature, regret should be better explained with the basic ideas of regret.

The average and weak regret definitions used in the paper are commonly used notions of regret in existing works on contextual dueling bandits (Saha, 2021; Bengs et al., 2022; Li et al., 2024). Thus, we also consider average and weak cumulative regret and provide regret bounds for them. By definition, average regret is the difference between the maximum latent reward and the average of the latent rewards of the selected arms, while weak regret is the difference between the maximum latent reward and the maximum of the latent rewards of the selected arms. We have revised the paper to highlight these points.

As the authors provide two algorithms, the reviewer would like to know some comparisons between these two. While some comparative simulation results are provided, could you also include a more qualitative analysis, incorporating some mathematical insights, to highlight the differences between the two algorithms?

The only difference between the UCB-based algorithm (NDB-UCB) and the TS-based algorithm (NDB-TS) is how these two algorithms select the second arm.

The second arm for NDB-UCB is selected (as given in Eq. (3)) as follows:

While the second arm for NDB-TS is selected (Line 202-203) as follows:

\widetilde{\mathbf{H}}_{p,q}^{(1)} = \mathbf{\Sigma} _{p,q}^{(1)} = \langle x _{(p)}, x _{(q)}  \rangle , 

\mathbf{A}_{p,q}^{(l)} = \begin{pmatrix} \mathbf{\Sigma} _{p,p}^{(l)} & \mathbf{\Sigma} _{p,q}^{(l)} \\ \mathbf{\Sigma} _{p,q}^{(l)} & \mathbf{\Sigma} _{q,q}^{(l)} \end{pmatrix},

\mathbf{\Sigma} _{p,q}^{(l+1)} = 2\mathbb{E} _{(u,v)\sim\mathcal{N}(0,\mathbf{A} _{p,q}^{(l)} ) } [\max(u,0)\max(v,0)],

\widetilde{\mathbf{H}} _{p,q}^{(l+1)} = 2\widetilde{\mathbf{H}} _{p,q}^{(l)}\mathbb{E} _{(u,v)\sim\mathcal{N}(0,\mathbf{A} _{p,q}^{(l)} )}[\mathbb{1}(u \ge 0)\mathbb{1}(v \ge 0)] + \mathbf{\Sigma} _{p,q}^{(l+1)}.

Dear Reviewer kAG9,

Thank you once again for taking the time to review our paper and provide thoughtful and valuable feedback. We hope that our rebuttal has addressed your concerns.

As the discussion period approaches its conclusion, we kindly ask if we could address any additional questions or comments. If you think that our responses have sufficiently addressed your concerns, we would be truly grateful if you could consider improving your evaluation of our paper.

Best,
Authors

We would like to thank the reviewer for taking the time to review our paper. We also thank the reviewer for appreciating our contributions and acknowledging our realistic modeling, rigorous theoretical analysis, and practical applications of our results in areas like RLHF. We have answered each of your questions as follows:

Real-World Dataset Evaluation: Have you considered evaluating your algorithms on real-world datasets, such as those from recommendation systems or search logs, to demonstrate their practical applicability and effectiveness?

Our experiments were primarily designed to validate our theoretical results and demonstrate that our proposed algorithms outperform existing contextual dueling bandit approaches, particularly when the underlying reward function is non-linear. To illustrate this, we use two synthetic functions, Square and Cosine, which are commonly used in earlier work on neural bandits (e.g., Zhou et al., 2020; Zhang et al., 2021; Dai et al., 2023). These controlled experiments provide a rigorous environment for evaluating algorithmic performance and verifying theoretical results.

Computational Efficiency and Scalability: Can you provide insights into the computational complexity of your algorithms? How do they scale with the number of contexts and arms, and are there strategies (e.g., model compression, online learning techniques) to mitigate computational overhead?

To discuss the computational efficiency and scalability of our proposed algorithms, we consider the following two key aspects:

Size of the neural network (NN): The primary computational complexity of our proposed algorithms is from the NN used to estimate the latent reward function. Let $d$ be the dimension of the context-arm feature vector (input dimension for the NN). Assume the NN has $L$ hidden layers, each with $m$ neurons. Then, the inference cost from the input layer to the first hidden layer is $O(dm)$, the inference cost for hidden layers is $O(Lm^2)$, and the inference cost for the final layer is $O(m)$. Therefore, the overall inference cost for each context-arm pair is $O(dm + Lm^2 + m)$. Note that $p=dm + Lm^2 + m$ is the total number of NN parameters (as discussed in Line 141). The training time for the NN is $O(ECLm^2)$, where $E$ is the number of training epochs and $C$ is the number of context-arm pairs observations. Therefore, choosing the appropriate size of NN for the given problem is very important, as having smaller NNs may not accurately approximate the latent reward function, while larger NNs can incur significant training and inference costs.

Number of contexts and arms: Let $K$ be the number of arms and $p$ be the total number of NN parameters. Since we use the gradients with respect to the current estimate of NN as context-arm features, the gradient computation cost for each context is $O(Kdp)$, where $d$ is the dimension of the context-arm feature vector. The computational costs for computing reward estimate and confidence terms are $O(Kp)$ and $O(Kp^2)$, respectively. For selection arms, the computational cost for the first arm is $O(Kp + K)$, which includes estimating the reward for each context-arm pair $O(Kp)$ and then selecting the arm with the highest estimated reward $O(K)$; and the computational cost for the second arm is $O(Kp + (K-1)p^2)$, i.e., computing estimated reward $O(Kp)$ and confidence terms $O((K-1)p^2)$ for all arm with respect to the first selected arm Thus, the overall computational cost of our proposed algorithms for selecting a pair of arms for each context is $O(Kdp + Kp^2)$. Since each context-arm pair is independent of others, each arm's gradients, reward estimate, and optimistic term can be computed in parallel. Consequently, the computational cost for selecting a pair of arms for each context can reduced to $O(dp + p^2)$.

This discussion has been added in Appendix C.1 of our revised paper.

Comparison with Other Non-linear Methods: How does your approach compare to other non-linear bandit algorithms, particularly those leveraging Gaussian processes or deep kernel learning?

Gaussian processes (GPs) and kernel-based methods are indeed popular choices for non-linear function approximation, but they have limited expressive power and fail when optimizing highly complex functions (Dai et al., 2023; Lin et al., 2023). While GPs are a better baseline than linear models, empirical studies have shown that GPs-based baselines perform poorly for the non-linear functions like Square and Cosine functions than neural network-based counterparts in contextual bandit settings (Zhang et al., 2021; Dai et al., 2023). In our revised paper version, we will also add Gaussian processes-based baselines.

Thank you again for your time and your careful feedback. We hope our answers will alleviate your concerns and improve your opinion of our work. If you have additional questions, we would be happy to address them.

We would like to thank the reviewer for taking the time to review our paper. We also thank the reviewer for acknowledging that our proposed algorithms address the shortcomings of existing algorithms and can be used to solve real-world problems with complex reward functions. We have addressed each of the weaknesses as follows:

If my understanding is correct, the problem formulation heavily relies on the link function $\mu$, whose properties significantly influence the regret bound, particularly through terms such as $\kappa_\mu$ and $L_\mu$.

You are correct that our problem formulation and regret bound depend on the link function $\mu$ (through $\kappa_\mu$ and $L_\mu$). However, this is in fact consistent with most previous works on dueling bandits (Saha, 2021; Bengs et al., 2022; Li et al., 2024) and bandits with binary feedback (Filippi et al., 2010; Li et al., 2017; Faury et al., 2020). Therefore, the use of the link function $\mu$ is widely accepted and has proven effective in facilitating the development of useful algorithms in both theory and practice.

Furthermore, unlike conventional stochastic bandit works, this paper assumes the reward feedback associates with the sub-Gaussian noise, which in this case, depends on the chosen link function. Typically in stochastic bandit settings, sub-Gaussian noise is independent of the learning formulation and is determined solely by environmental settings, which makes this formulation unnatural.

We would like to clarify that we do not assume that the reward feedback is associated with sub-Gaussian noise. Instead, in our problem formulation, the noise $\epsilon_t=y_t-\mu(f(x_{t,1})-f(x_{t,2}))$ is guaranteed to be conditionally 1-sub-Gaussian, which we have discussed briefly at the end of Section 3.4.1 and shown in more detail in the proof of Lemma 8. We give a brief explanation here: Firstly, note that given the history $F_{t-1}$, we have that $\mathbb{E}[\epsilon_t|{F}_{t-1}]=0$; next, since $y_t\in\{0,1\}$ and $\mu(\cdot)\in[0,1]$, we also have that $|\epsilon_t| \leq 1$. Therefore, $\epsilon_t$ is guaranteed to be conditionally 1-sub-Gaussian. For more details, please see the proof of Lemma 8 in Appendix A.2. Therefore, the 1-sub-Gaussian property of the noise $\epsilon_t$ does not depend on the link function, as long as $\mu(\cdot)\in [0,1]$.

Additionally, in Assumption 1, $\mathcal{X}$ is not clearly defined. Does $\mathcal{X}$ represent the entire arm context space with $X_t \subset \mathcal{X}$? If so, how would the learner possess prior knowledge of $\mathcal{X}$ to select the optimal $\kappa_\mu$ value for exploration (i.e., the $\beta_T$ term in Equation 3)? A similar issue also exists for $\widetilde{d}$, as it is unrealistic to assume the learner has prior knowledge of this parameter.

Firstly, in Assumption 1, you are correct that $\mathcal{X}$ represents the entire arm context space with $\mathcal{X}_t\subset\mathcal{X}$. We have added the definition of $\mathcal{X}$ at the end of the first paragraph in Section 2 (Lines 95-96 in the revised paper). Thank you for pointing this out.

In addition, the dependence of the exploration parameter $\beta_T$ on $\kappa_\mu$ (and hence on $\mathcal{X}$) is, in fact, very common in dueling bandits and bandits with binary feedback (Saha, 2021; Bengs et al., 2022; Li et al., 2024). Similarly, the dependence of the exploration parameter $\beta_T$ on $\widetilde{d}$ is prevalent in neural bandits (Zhou et al., 2020; Zhang et al., 2021). In practice, we do not need to have prior knowledge of the values of $\kappa_\mu$ and $\widetilde{d}$ to calculate $\beta_T$. Instead, following the common practice of previous works, we can simply set the exploration parameter $\beta_T$ to be a constant.

Dear Reviewer uMSZ,

Thank you once again for taking the time to review our paper and provide thoughtful and valuable feedback. We hope that our rebuttal has addressed your concerns.

As the discussion period approaches its conclusion, we kindly ask if we could address any additional questions or comments. If you think that our responses have sufficiently addressed your concerns, we would be truly grateful if you could consider improving your evaluation of our paper.

Best,
Authors

Thank you very much for the rebuttal. Since no additional experiments on real datasets related to LLM modeling have been introduced, my primary concern regarding the experiments remains unresolved. From my personal opinion, the current empirical evaluation can fail to adequately support the main motivation of this paper. I have decided to keep my score.

We would like to thank the reviewer for taking the time to review our paper. We also thank the reviewer for acknowledging that our results are significant contributions to bandits. We have addressed the weakness you mentioned as follows:

However, for the regret analysis, the authors still require the NTK gram matrix to be positive definite. This assumption can be a limitation in real-world applications, as it can be easily violated by repeating observed arm contexts, thereby hindering the practicality of the proposed methods.

The assumption of a positive definite NTK gram matrix is, in fact, a common assumption adopted by previous works on neural bandits (Zhou et al., 2020; Zhang et al., 2021). In addition, this assumption is only needed in our theoretical analysis and is hence not required in the practical deployment of our algorithms. In other words, in real-world applications, even if arm context observations are repeated (i.e. if the NTK gram matrix is not positive definite), neural bandit algorithms (including ours) can still be applied. For example, in the work of Lin et al. (2023), a neural bandit algorithm is used to solve the problem of instruction optimization with a discrete domain (in which the input observations are easily repeated) and still achieves outstanding performance. Therefore, this assumption, which is only needed in our theoretical analysis, does not hinder the practicality of our proposed methods.

Thank you again for your comments. We hope our clarification could improve your opinion of our work. If you have additional questions, we would be happy to address them.

Dear Reviewer nPZh,

Thank you once again for taking the time to review our paper and provide thoughtful and valuable feedback. We hope that our rebuttal has addressed your concerns.

As the discussion period approaches its conclusion, we kindly ask if we could address any additional questions or comments. If you think that our responses have sufficiently addressed your concerns, we would be truly grateful if you could consider improving your evaluation of our paper.

Best,
Authors