Tackling Biased Evaluators in Dueling Bandits

Thank you for your suggestion and identifying this work as one that is the "first work to address the dueling bandits problem under biased feedback", with "solid theoretical foundation", and "comprehensive and rigorous experimental evaluation".

Regret Bound Analysis: We appreciate your valuable comments on the regret bound and agree with your statements. To address this comment, we have tried our best to improve the bound. The improved bound is sublinear for all $B \triangleq |\mathcal{B}|$'s. The main improvement is on inequality (f) in (42).

• Original Version: We bound $Z(t)$ using inequality (f) by enumerating all possible cases (i.e., all possible values of $n_{ij}^b(t)\triangleq N^b_{ij}(t)+N_{ji}^b(t)$) and relaxing every term (each corresponding to a case) by an upper bound of one. This relaxation essentially considers each case being upper-bounded by the same value and occurring with equal chance in $\mathbb{E}[\sum_{t}Z(t)]$ in (44). However, based on our proposed algorithm, some sets of $n_{ij}^b(t)$ may occur with a very small chance. For example, for a specific $(i,j)$ pair, consider the case where the values of $n_{ij}^b(t)$ for four different $b$'s are 1, 1, 1, and 1000, respectively. This case rarely happens in our proposed algorithm, because the algorithm tends to explore arm pairs independently for evaluators with different bias levels, making the exploration times rarely highly skewed.
• Improved Version: We provide a better bound of $\mathbb{E}[\sum_{t}Z(t)]$ by considering the different probabilities that cases occur. Specifically, we introduce an event:

Intuitively, this is the event where the exploration is highly skewed among evaluators, as the previous example suggests. Then, we decouple $Z(t)$ into two terms: $Z_1(t)$, containing terms of cases where event $X_{ij}(N_{ij},t)$ holds; $Z_2(t)$, containing terms of cases where event $X_{ij}(N_{ij},t)$ does not hold. We can prove that (i) the probability of event $X_{ij}(N_{ij},t)$ is small, and (ii) each terms in $Z_2(t)$ is upper-bounded by a value that is much smaller than one if the associated pair $(i,j)$ has been explored for more than $m(t)=B^2\log(Bt^{2\alpha})$ times. As a result, when we take the expectation in (44), $\mathbb{E}[\sum_{t}Z_1(t)]$ is small due to the small probability, and $\mathbb{E}[\sum_{t}Z_2(t)]$ is upper bounded by a smaller bound of $\mathcal{O}(\sqrt{BT})$, because majority of the terms are upper bounded by a value smaller than one.

Based on the improvement, the upper bound for $\mathbb{E}[\sum_{t}Z(t)]$ changes from $\mathcal{O}(T)$ in the original version to $\mathcal{O}(\sqrt{BT})$. Note that $B$ is the number of available bias; if the bias space is continuous (i.e., $b\in[0,1]$), $B$ can be regarded as the number of intervals for discretizing the bias space. So $B$ is usually much smaller than $T$, so the bound becomes tighter. Also, $B$ is a constant value independent of $T$. Thus, the round-average regret improves from $\mathcal{O}(\sqrt{\log{T}})$ to $\mathcal{O}(\sqrt{B\log{T}/T})$ and hence sublinear.

For the experimental results, we have shown the convergence of the regrets in Figure 1 of Appendix J.2. The regret of our proposed algorithm appears to be sublinear.

To address your comments, we will include this improved version in the manuscript. Despite that, we would like to clarify that although the recent bound analysis in the manuscript can be improved as above, this is the first work towards understanding the biased evaluators in dueling bandits and makes contributions in many of the other aspects:

• We identify the novel problem of biased evaluators in dueling bandits.
• We propose a dueling bandits algorithm for known bias case, which is not a simple transformation but requires careful design. We provide the first bound of the regret under the known bias case, overcoming challenges of heterogeneous bias level and complex formulation of the estimators.
• We overcome the challenge of non-convex problem of the joint bias and winning probability estimation and propose a block coordinate descent (BCD)-based approach for unknown bias case to solve the joint estimation problem.
• Our approach can be incorporated into existing dueling bandits approach, e.g., RC, RUCB, DT, to further improve their robustness under biased evaluators. Experiment results validate the our proposed approaches outperform the baselines in average and weak regrets.

Weak Regret and Average Regret: We agree with your comment. In the theoretical analysis, we essentially prove the bound on average regret. For the weak regret, we relax it to be an average regret in (33) of the proof, so the bound may be loose. To avoid over-claiming our contribution on proving the bound of weak regret, we will clearly state this in the manuscript.

The Inclusion of $\xi(t)$ for Unknown Bias Case: We acknowledge that it will be helpful to provide the specific form of $\xi(t)$ in the bound analysis. However, this is very challenging, and we admit not being able to handle it at this moment. This is because the joint bias and winning probability estimation in (17) is a non-convex problem. Analyzing the optimality of solving a non-convex problem using BCD algorithm is an open problem, even in the area of mathematics. This is the main limitation of this work, and we will state it clearly in the manuscript. Despite this limitation, we would like to remind that this work has made substantial contributions as discussed above. We hope that this work can motivate further studies on algorithm design and analysis in the future.

Existence of a Ground-Truth Pairwise Preference Matrix: We would like to clarify that it is a performance matrix but not a preference matrix. "Performance" emphasizes on the intrinsic quality of the LLM, while "preference" corresponds to user's own opinion. We use the pairwise performance matrix to characterize the ground-truth performance of the LLMs, i.e., the probability that an LLM is better than the other LLM considering all possible queries. Although this ground-truth may not be observed in practical systems, it can be defined as the average pairwise performance of LLMs across query space. We agree with the reviewer that "the LLM outputs are inherently subjective and user-dependent", i.e., the preference can deviate from the pairwise performance. This is the reason that motivates the consideration of user bias (i.e., user-specific preference) in the system model, e.g., some users are not sensitive to the outputs of diverse LLMs. We will clarify this point in the manuscript.

Uniform Bias: Thank you for pointing out this. As the first attempt, this work considers a uniform bias for a given evaluator across all arm pairs. For example, consider a scenario where the evaluators belong to perfect evaluators, spammers (who randomize among choices), or attackers (who always choose the opposite result). In this case, the bias is the intrinsic feature of evaluators regardless of the arm pairs. We will mention the potential extension of arm-dependent bias modeling in the manuscript.

Elaboration on Addressing the Challenge of Bound Analysis: The main difficulty comes from the complex form of the arm performance estimation and confidence radius. In particular, those are in the form of weighted sum of the feedback statistics from diverse biased evaluators. To address this, we prove new inequalities to support the bound analysis. Inequality (g) in (42) is the most important one. In this part of analysis, we transform the problem of finding an upper bound of the expression before (g) as finding the upper bound of the optimization problem given in (43), based on which we determine the upper bound of the optimization problem by analyzing the optimal solution of it in Appendix E.2.

Analysis on the Incorporation of Bias Estimation to Baselines: Since most of the proofs in dueling bandits (e.g., UCB-based, Bayesian-based) involve the determination of the confidence radius and build upon the probability that the estimation falls within and outside the radius, we would expect that the related proof techniques on confidence radius can be applied to prove the regret bound of those baselines. However, additional techniques for accounting the specific arm performance estimation and selection approach will be needed. Take double Thompson sampling approach as an example. The arm is chosen using sampling rather than a deterministic approach, so additional stochastic behavior related to the sampling needs to be incorporated. Overall, we believe that the recent proof can help with their regret bound analysis, but further efforts are needed, which is out of scope of this paper.

Confidence Radius in Lemma 3: If we substitute $\eta_m$ with its estimate $\hat{\eta}_m$ into the expression in Lemma 3, then by rearranging the terms, the confidence radius in Lemma 3 is exactly the same as the confidence radius in (19) used in Algorithm 2. Note that this does not imply that if we substitute $\hat{\eta}_m$ with $\eta_m$ into (19), then we can directly obtain the actual confidence radius in (20). This is because the confidence radius corresponds to the radius where an estimation of arm performance falls within the radius (centered around the actual arm performance) with a sufficiently high probability, so the actual confidence radius is a function of both the actual bias $\eta_m$ and the estimated one $\hat \eta_m$.

Typos and Formatting: We will address them in the manuscript.

Thank you for your suggestions and for identifying the strength of this work on "general preference" setting, "general" estimation approach, and the "crucial" investigation of bias.

Finite Arms and Evaluators: We would like to clarify that in the LLM example, the number of arms (i.e., LLMs) and the number of evaluators (i.e., humans) are finite in practice. Although the number of evaluators can be huge, each person frequently interacts with LLMs and provides feedback, under which it is still possible to estimate the bias of evaluators and hence estimate the arm performance.

Bias Due to Contextual Information: Thank you for pointing out this interesting point. We agree with the reviewer that the performance of LLMs depends on contextual information and the available contexts can be infinite. First, this is the reason why we introduce a probability-based performance model for arms, i.e., the pairwise comparison outcome between two arms is modeled as a random variable rather than being deterministic, as most of the works on dueling bandits (Bengs et al., 2021). Second, we agree with the reviewer that incorporating contextual information for arm comparison can better characterize the scenario in the motivating example. To achieve this, one potential idea is to incorporate contextual information into the winning probability modeling (Ong et al. 2025). In this case, we need to take into account the context similarity in the arm performance and bias estimation. Overall, this work aims to investigate a general dueling bandits scenario instead of working on a specific application scenario, so as the first step, we simply the model by focusing solely on the impact of biased evaluators on dueling bandits. We will include these discussions in the manuscript to alleviate the potential confusion.

I. Ong, A. Almahairi, V. Wu, W. Chiang, T. Wu, J. E. Gonzalez, M. W. Kadous, and I. Stoica, " RouteLLM: Learning to Route LLMs from Preference Data," Proc. ICLR, Singapore, April 2025.

Advantage and Disadvantage of Optimality Definition: In this work, we choose to consider the Borda winner for two reasons. First, it is commonly considered in dueling bandits, as shown in Tables 6 and 7 of the survey paper (Bengs et al., 2021). Second, it reveals the overall probability that an arm wins over other arms. Specifically, the Borda winner is the arm with the highest winning probability. This is in contrast to, for example, ​​the Copeland winner, which is the one that beats more arms (but possibly with a winning probability only slightly higher than 0.5). Considering the motivating example of LLM inference with diverse queries, the Borda winner could be more suitable, as a higher overall winning probability likely indicates a higher chance that users are satisfied with the inference results.

We agree with the reviewer that defining the optimality using the Borda winner has limitations. From the theoretical perspective, one major limitation of the Borda winner is that it may sometimes not be consistent with the Condorcet winner (if it exists). This Condorcet winner is the best arm among arms if a total ordering of arms exists. However, the Condorcet winner does not usually exist in practical systems (Bengs et al., 2021), e.g., there may not exist an LLM that is better than all other LLMs for all kinds of queries. Thus, the aforementioned limitation may not be a major concern. On the other hand, in terms of neglecting minorities in the annotator pool, each annotator's preference/feedback contributes to the winning probability of arms with an equal weight in the Borda winner. Thus, our model does not neglect or exclude minority opinions. Thank you for pointing out this valuable point. We will include these discussions in the manuscript.

Experiments with More Arms/Evaluators and Preference Model: Due to the space limit, we place some of the experiments in the Appendix. We have conducted experiments with up to 100 arms and 100 evaluators. Please refer to Table 7 in Appendix J.4 for details. In addition, we have evaluated the impact of the preference model by varying the arm heterogeneity. Please refer to Tables 1, 3, and 4 for details.

Sublinearity Result Being Consistent with Existing Works: With this statement, we mean that if there is no bias, then the order of the regret bound of our algorithm is the same as those in the existing works that did not consider bias, e.g., [13]. The order is with respect to $T$. Specifically, our regret is at the order of $\mathcal{O}(\sqrt{\log{T}/(T\Gamma^2)})$, where $\Gamma$ can be regarded as a constant value; in [13] which did not consider bias, its algorithm achieves a regret at order $\mathcal{O}(\sqrt{\log{T}/T})$. It can be seen that they have the same order with respect to $T$. We will include this explanation in the manuscript.

Explanation on Highly Coupled: The "highly coupled" of the arm performance and bias estimation means that the estimation of arm performance is a function of the estimated bias in (16), and the estimation of the bias is a function of the estimated arm performance in (18). In this case, we cannot estimate them in a sequential manner, i.e., one after the other. It is also challenging to estimate them simultaneously due to the non-convexity of the estimation problem. Also, an inaccurate estimation of one of them will lead to an inaccurate estimation of the other, making the algorithm design difficult. We will include the explanation in the manuscript.

Explanation and Evaluation on "Update Twice": The following shows the evaluation of different times of updates. Note that to show a relatively obvious performance gap, we conducted experiments under a larger scale setting than that in Table 1, which has 50 arms and 10 evaluators.

It can be observed that "updating twice" leads to the best performance. Further increasing the times can degrade the performance. This result will be included in the Appendix. Then, we would like to explain the intuition for "updating twice". The main idea is to find a better initial point for a more accurate estimation in each iteration. According to Algorithm 2 in Appendix F, in line 2 of each iteration, the arm performance estimation $\hat p_{ij}(t-1)$ is initialized as the estimation ignoring the bias, and then the bias estimation $\hat \eta_{m}(t-1)$ is initialized based on the recent arm performance estimation $\hat p_{ij}(t-1)$. Note that up to now, it is obvious that both the bias and arm performance are far from an ideal initial point for estimation update, because they are determined by ignoring the bias. To address, in line 4, we update $\hat p_{ij}(t-1)$ and $\hat \eta_{m}(t-1)$ for the first time. This step leads to a better initial point (for estimation update) by considering the bias. After that, the second update of $\hat p_{ij}(t-1)$ and $\hat \eta_{m}(t-1)$ corresponds to the actual updates of the estimation.

Cumulative Regret Curve: The cumulative regret curves are provided in the Appendix due to the space limit. Please see Figure 1 in Appendix J.2 for details.

Additional Baselines: Thank you for your suggestion. We have conducted experiments on Doubler, MultiSBM, MaxInP, and MaxMinLCB. The following provides the experimental results on weak and average regrets respectively.

The results show that our proposed approaches BS-K and BS-UN outperform the baselines in both weak and average regrets. We will include them in the manuscript.

Thank you for your suggestions and identifying the strength of this work on "theoretically grounded", being "motivated well", and "well-written".

Bias Distribution: Thank you for pointing this out. We have conducted experiments under different bias distributions. Due to the space limit, some of the results are presented in the Appendix. Here are the details:

• Different Beta Distributions: In the experiments, we use $\alpha_{\text{B}}$ in the beta distribution to characterize the impact of bias. A smaller $\alpha_{\text{B}}$ implies a higher degree of evaluators’ bias. Please refer to Tables 1, 3, and 4 for the results. As the reviewer expects, our proposed approaches are more beneficial when the bias is more severe. Take the weak regret in Table 1 as an example. When $\alpha_{\text{B}}$ decreases from 3.0 to 1.0, the regret reduction improves from 13.0%-83.8% to 89.5%-96.8%.
• No Bias: Please refer to Table 8 in Appendix J.6. For the weak regret, the results of the baselines range from 11 to 154, and the best performance among our approaches is 31. For the average regret, the results of the baselines range from 148 to 1524, while the best performance among our approaches is 126, which is superior to the baselines. In summary, our proposed algorithms may lead to a performance degradation when there is no bias. However, the degradation may not be large, indicating a capability to correctly recognize the absence of bias.

Relative UCB: We have conducted experiments on Relative UCB, which is denoted by "RUCB" in the manuscript.

Weak and Average Regrets: Thank you for pointing this out. We agree with your statements. In the theoretical analysis, we essentially prove the bound on average regret. For the weak regret, we relax it to be an average regret in (33) of the proof, so the bound can be loose. Due to this reason, our analysis cannot be applied to strong regret. We will state this point clearly in the manuscript.

Synthetic Data: This work is more likely to be a theoretical work (rather than an application work), so we use synthetic data in experiments. This provides us with a more systematic way to understand how bias distribution affects the algorithm performance. We agree with the reviewer that experiments with real-world bias data can help to validate the algorithm performance in practical systems. However, this is very challenging during the short rebuttal period, and we will include it in the future work.