Tackling Biased Evaluators in Dueling Bandits
Authors: Ming Tang
Yuxuan Zhou
Chao Huang
Venue: NeurIPS 2025 spotlight ()
Keywords: Dueling Bandits; Evaluation Bias
Primary area: theory

Abstract: In dueling bandits, an agent explores and exploits choices (i.e., arms) by learning from their stochastic feedback in the form of relative preferences. Prior related studies focused on unbiased feedback. In practice, however, the feedback provided by evaluators can be biased. For example, human users are likely to provide biased evaluation towards large language models due to their heterogeneous background. In this work, we aim to minimize the regret in dueling bandits considering evaluators’ biased feedback. We begin with a benchmark case where evaluators’ bias information is known. Solving the known-bias case is nontrivial, because the bias cannot be easily decoupled from the feedback. We overcome this challenge and propose an unbiased arm performance estimator and a bias-sensitive dueling bandits algorithm. We manage to analyze the regret, dealing with the complex form of the estimator, and show that the feedback either matching or opposing the ground-truth reduces the regret. Then, we study the case where evaluators’ bias information is unknown. The associated estimator can hardly be solved in closed-form due to the non-convexity of the estimator solving problem. We address this challenge and propose an extended bias-sensitive algorithm by incorporating block coordinate descent. This algorithm is proven to achieve the same order of regret (as in the known bias case) with a bounded error. Experiments show that when compared with baselines, our algorithms reduces the regret by up to 86.9%.

Tackling Biased Evaluators in Dueling Bandits
Ming Tang
Yuxuan Zhou
Dept. of Computer Science and Engineering Southern Univ. of Science and Technology Shenzhen, Guangdong, China tangm30sustech. edu.
Dept. of Mathematics
Southern Univ. of Science and Technology
Shenzhen, Guangdong, China
zhouyx8@mail www.ech.sssshhcc.eco edu.
Chao Huang School of Computing
Montclair State University Montclair, New Jersey, USA
huangch@montclair.ce
Abstract
In dueling bandits, an agent explores and exploits choices (i.e., arms) by learning from their stochastic feedback in the form of relative preferences. Prior related studies focused on unbiased feedback. In practice, however, the feedback provided by evaluators can be biased. For example, human users are likely to provide biased evaluation towards large language models due to their heterogeneous background. In this work, we aim to minimize the regret in dueling bandits considering evalu- ators' biased feedback. We begin with a benchmark case where evaluators' bias information is known. Solving the known-bias case is nontrivial, because the bias cannot be easily decoupled from the feedback. We overcome this challenge and propose unbiased bandits algorithm. We manage to analyze the regret, dealing with the complex form of the estimator, and show that the feedback either matching opposing the ground-truth reduces the regret. Then, we study the case where evaluators' bias information is unknown. The associated estimator closed-form due to the non-convexity of the estimator solving problem. We address this challenge and propose extended bias-sensitive algorithm by incorporating block coordinate descent. This algorithm is proven to achieve the same order of regret (as in the known bias case) with bounded error. Experiments show that when compared with baselines, our algorithms reduces the regret by up to 86.9%.
performance estimator and bias- dueling
hardly be solved in
Introduction
1.1 Motivation and Background
Multi-armed bandit (MAB) [ a widely used approach for online learning. It explores and exploits given set of choices (i.e., arms) to minimize long-term regret. In standard MAB, the reward of the selected arm is commonly represented by real number, e.g., if pulling an arm of slot machine returns 5 dollars, then the reward can be represented by 5. As result, the exploration and exploitation decisions can be made based on these real-valued reward feedback. However, systems, the real-valued reward feedback is unavailable. For example, consider a company that aims at providing its users with high-quality user experience for question answering tasks by selecting
many practical
Corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

from various large language models (LLMs), e.g. GPT-4 (2). where these LLMs can be thought of arms. Unlike prediction and classification, the output of an LLM is usually paragraphs that are intrinsically subjective. Their ground-truth quality is hard to measure or may not even exist. This
makes difficult to use a real-valued reward to represent the quality of and select an L.M (3 4.
To address the unavailability of real-valued reward feedback, existing studies (c.g., [4 14) evaluated
arms based on qualitative comparison between pair of arms, which are referred as dueling bandits. In these approaches, an agent selects two arms in each round for comparison. The agent then observes the qualitative comparison result between the two arms, based on which the agent makes exploration and exploitation decisions. Interested readers can refer to [5] for comprehensive survey.
Although these studies (e.g.. [3]33) addressed the lack of real-valued reward feedback, they did not consider an important scenario where the feedback is provided by biased evaluators. For example, [6] suggested that the L.LM selection of company (which serves as agent) should be based on its users' feedback. However, the users (who serve as evaluators) are humans. Their feedhack may be biased due to various factors, e.g., users' expertise or demographic background. Biased feedback can significantly degrade the performance of conventional dueling bandits approaches and increase the long-term regret. We empirically show that the presence of biased evaluators increases the regret of baselines by an average of 8.44 folds (see Appendix K.8)
Some recent studies (e.g., [17 [8] considered biased feedback in conventional MAB settings. However, those approaches are not applicable in dueling bandits due to a lack of real-valued rewards. Other studies (e.g., [19 [1) considered pairwise assessment with bias in mobile crowdsourcing, while their goal is to find the best choice or the ranking of choices without considering the long-term sxploration-exploitatoon tradeoff. Thus, their algorithms and analytical frameworks are not applicable to dueling bandits. While adversarial dueling bandits (e.g., (22)) emphasized time-varying winning probability matrices of arms, they do not consider evaluator-specific biased feedback.
1.2 Solution and Approach
In this work, we take into account the feedback provided by biased evaluators and propose bias- sensitive upper confidence bound (UCB) algorithms with performance guarantee. Our proposed approach for addressing biased evaluators can be readily extended to other dueling bandits algorithms (e.g., relative confidence [10), relative UCB (TT), double Thompson sampling (12) and improve their performance (see S5c Specifically, we aim answer the following questions:
Q1 How can we design an unbiased estimator for arm performance and low-regret dueling bandits algorithm in the presence of evaluators' bias?
Q2 What is the performance guarantee of our algorithm?
Answering QI is challenging. (i) The bias of evaluators is usually unknown a priori. Thus, the algorithm design requires joint estimation of the evaluators' bias and the winning probability of arms, which makes the corresponding estimator solving problem non-convex. (ii) Even when the bias of evaluators is known, such design is non-trivial. An intuitive solution is to directly decouple the bias from the observed feedback by equation transformation. However, this is proven to induce an unbounded regret. We overcome the challenge by transforming the estimator design problem into convex optimization problem and theoretically derive an unbiased estimator and its confidence radius.
Answering Q2 is non-trivial, the determined estimator and confidence radius from Q1 involve evaluators' heterogeneous bias levels, which makes the regret analysis for conventional dueling ban- dits inapplicable. We overcome this challenge by applying equation transformation and introducing auxiliary inequalities to support the regret analysis and derive the regret of our proposed algorithms.
Our main contributions are listed as follows:
To the best of our knowledge, this is the first attempt that considers biased evaluators in dueling bandits. Our approach is applicable to general arm performance models with deter- ministic winning probability and general bias models that model feedback with conditional probability. Meanwhile, it can be incorporated into existing dueling bandits approaches to reduce their regrets under the presence of evaluators' bias.
We begin with the case where each evaluators' bias level is known. We overcome challenge Q1-(ii) and propose a bias-sensitive UCB algorithm. To address Q2, we theoretically derive the long-term regret. Analytical results show that our proposed algorithm achieves

---

a sublinear regret, which is of the same order to those in conventional UCB algorithms of dueling bandits.
We further study the case where each evaluators' bias level is unknown. We overcome challenge Q1-(i) by decoupling evaluators' bias from arm performance estimation when initializing estimators and incorporating block coordinate descent (BCD) [23). We propose
an extended bias-sensitive UCB algorithm, and prove that this extended algorithm achieves the same order of regret as in the known bias case with a bounded error.
Experiments show that when compared with five baselines, our algorithms reduces the regret by up to 86.9%. The reduction is more significant when the bias levels among evaluators are more hetcrogeneous. Meanwhile, our estimator can be incorporated into baselines and reduces their regrets by up to 75.9%.
System Setup
We consider agent and set of M evaluators M = (1.2...., M) whose feedback can be biased. There are a total K arms, denoted by set K. = {1, K3. In each time slot E T (1,2,... T), an arbitrary evaluator arrives. The agent selects two arms for the evaluator. We consider a setting where the evaluator evaluates the selected arms and, at the same time, provides pairwise comparison feedback for the arms. Consider LLM evaluation as an example. A company (agent) selects two LLMs (arms) to serve its users (evaluators). The users observe the inference output of the LLMs and provide pairwise comparison feedback for the two LLMs. The goal of the agent is to minimize the long-term regret of the selected arms (roughly speaking, maximize the chance that the best arm is selected) based on the evaluators' feedback
Arm Model: We consider a stochastic setting where an arm outperforms another arm with certain probability [15). This probability is associated with the ground-truth performance of arms and cannot be observed directly. Let o; > Oj denote an observation that arm E K. outperforms arm j E A, and let Pr(o: > 0j) denote the probability that arm i outperforms j. For ease of presentation, we denote
Psj A Pr(o; > 0,).
(1)
We assume Pr(o; > 0z) Pr(o; - <z;)) 1, and do not consider the case where comparing and 0j leads to tie. As suggested by (24). ties can handled by giving "half a point" to both arms, reducing the problem
tie-free case. Note that probability model in generalizes various models as special cases, c.g., Bradlcy-Terry (BT) model [2I] and Logistic model 225.
In dueling bandits, Condorcet winner (i.c., an arm i with Pıj > 1/2 for all j E K. {i)) may not exist [5). As in many related works (e.g.. 13 14). we define the best arm using Borda score:
0, 2 K-1 Σ Ejex(()) Pij.
Intuitively, a larger O; implies a higher probability that arm i beats other arms on average. This metric is suitable. For example, in LLM evaluation, a higher winning probability implies higher chance that users are satisfied with the inference results of the LLM. We consider Borda winner [13 14
Definition 1 (Borda Winner). The best arm i is the arm with the highest Borda score, i.e., arg maxiex: Oz.
Evaluator Bias Model: We use o; >mm Oj to denote the case where evaluator m E M provides feedback claiming that arm i outperforms arm j. Note that >m 0j and 0, > 0g may not match due the bias of evaluator m. There are various types of evaluators' bias. In this work, we follow mobile crowdsourcing studies (c.g.. (21)) and introduce coefficient 7m to characterize the probability that evaluator m reveals a feedback that matches the ground-trutl comparison result:
mm Pr(o; >m Oj o, > 0,).
2 FAlthough we use L.M as a motivating example, this work focuses on a general dueling bandits scenario without targeting any particular application. To adapt it to the LLM setting. additional factors such as contextual information would need to be incorporated into the
selection and comparison process.
'Despite the rationale of using Borda winner, it may sometimes be inconsistent with the Condorcet winner (if exists). Thus, if finding the Condorcet winner is the primary goal, although our algorithms can still lead to superior performance (see Section 5). the theoretical analyses in this work may longer be applicable.
3

---

That is, given the fact that o; > Oj, evaluator m with bias 7m claims Fm o, with probability 7m- Note that Pr(o; 3mm Oj o > -;) + Pr(o; Xm Oj o > o₂) = Similarly, we exclude the case where the evaluator reports no difference between arms. If this case happens, the evaluator can randomize among the arms with equal probability and provides feedback. The bias model in (3) can characterize various types of bias, such as ambiguity in perception and comparison [26] and diverse roles of the evaluators (2I]. Consider bias resulting from diverse roles as an example. If 7mm = 1, then evaluator m is a perfect evaluator. If 7mm- = 0.5, then evaluator is spanmer who provides random feedback. If 7/m = O, then evaluator m is an attacker which aims to worsen the choice of the agent and always provides opposite feedback.
Based on (3), the probability that evaluator m claims arm outperforms arm j is given by
m - Pij
Pr(o: >mm 03) = -MmPii + (1 1m
Arm Selection and Regret: In time slot T. an evaluator arrives, and let m, E M denote this evaluator. The agent selects two arms z1 (t) E K and (t) E K for the evaluator using a dueling bandits algorithm (to be proposed in Sections 3 and 4 Let xtt) - {tz(t), xt)) Note that z1 (1) + x2(() must hold before algorithm convergence; otherwise, no comparison between arms is performed and hence there is no exploration in time l. After evaluator mh evaluates both chosen models xi (1) and (4), it sends a binary feedback to the agent, i.e., either (22(1) >m. (2)(() or Oz)(1) m. (z1(()- The binary feedback is commonly considered in dueling bandits (T5) and is suitable for the scenario that lacks rallev reward feedback from evaluators. Recall that in the
LLM example, it is easy for users to judge which output from the two LLMs is better, while it is difficult for them to give realevalued score for the outputs of LLMs.
In this work, we focus on both average regret and weak regret, which are commonly considered regrets in dueling bandits (1). The average regret RegA(x(t)) (t)) [10] 12] and weak regret (xt)) 27 are defined as the average and maximum Borda score among the two selected arms, respectively:
RegA(z(()) = 0,- - (02,(1) + (2)
(5)
(eg(()(()) = 0,- max (z)
(6)
For example, average regret refers the case where a user retrieves information from the inference outputs of both LLMs. Weak regret refers to the case where user is satisfied as long as one of the LLMs provides satisfactory output. Since all of our algorithms and theoretical results apply to both average regret and weak regret, we use Reg(z(t)) to denote them.
The goal is to minimize the long-term
regret:
[mt)) + Σ F (ee((x(()))
We solve problem 7 for both known and unknown bias cases in Sections 3 Jand respectively.
3 Known Bias Case
In this section, we start with the benchmark case where the evaluators' bias 7m is known. In practical systems, the bias could be obtained by running pre-evaluation tests, e.g., in the LLM example, the company may estimate user bias through offering queries whose ground-trute ttout answers are known, We consider the setting where the set of available bias is finite. That is, Mm B & {n/ . n for all m E M, where B- [B] and the superscript A is short for "available". As long as the number of evaluators is finite, this assumption on finite bias set holds.
We build our algorithm based on UCB. Despite this, our ideas for addressing biased evaluators can be incorporated into various baselines reduce their regret (see Appendix K.T.p Note that even for the known bias case, designing the algorithm is challenging. This is because when estimating the pairwise winning probability of arms, the bias cannot be easily decoupled from the observed feedback provided by evaluators. Meanwhile, the complex form of the winning probability estimator makes deriving the associated confidence radius and analyzing round-average regret further challenging.
3.1 Bias-Sensitive UCB Algorithm
We first present the unbiased estimation of pairwise winning probability of arms and confidence radius calculation respectively. Then, we show the algorithm details.

---

1) Unbiased Arm Performance Estimation: We aim to design an unbiased estimator of winning probability matrix - i.j E X.) which will be incorporated into our bias-sensitive UCB algorithm. Note that is possible to obtain an unbiased estimator by transforming the problem into conventional dueling bandits via decoupling the bias in 4 However, such an estimator is sensitive to the feedback of spammers, which can lead to an infinite average regret (see Appendix (A). To deal with this challenge, we first transform the estimator design problem into an optimization problem. Then, we solve the problem to obtain the estimator.
Let Ni (1) denote the number of feedback claiming o; 7m Oj. and its evaluator has a bias 7/m = 7 Let (t)(t) C B denote the set of bias index b such that (t) + ()) > 0. Designing an estimator p(t) (fig(t), i, E XC) is equivalent to finding the optimal estimator ptt) that minimizes the difference between the estimated value of Pij using the estimator and the approximate value (t) 2 No (1) + (t)). That is, p(t) minimizes the following problem:
min, (0 (n (1 mp)p - (t)
(8)
Problem contains R² x M terms, each corresponding to exactly one decision variable pij. Thus, problem can be equivalently transformed to set of sub- problems of P., (t):
(1) arg minp [| 15Pss + ctyl13
where Wiy (2 - 1,b E (1) C.j _ (1 (1-1 (1). Bi)())). Based on Karush-Kuhn-
Tucker (KKT) conditions, the optimal solution to problem ( satisfies (w (in))isst) -..
This results in the following unbiased estimator, with proof in Appendix
Lemma 1 (Arm Performance Estimator). After time slot t, the pairwise winning probability Pij in is estimated by
(t)(t)= EbEB, (1) (2 (2t) (1 -())
(10)
EbEB, (2ng - 1)
This estimator is unbiased, ie., (t)) = Pij. Based on (10). if an evaluator tends to be a spammer (i.e., Mm is closer 0.5), lower weight assigned the evaluator's 's feedback.
2) Confidence Radius Calculation: We now derive the confidence radius of the estimator in Lemma [ This analysis is more challenging than that in conventional dueling bandits, because the estimator is in the form of a weighted sum of the feedback statistics of evaluators considering their bias. The involved sum, weighting, and shift operations require additional matherattcal transformation to solve the confidence radius based on Hoeffding inequality. The proof is given in Appendix C
Definition (Confidence Radius). We define the confidence radius as Pr(lix, (1) - Payl S (()(()) Z
1 2/2", That is, (t) a one-dimensional bound such that (pr, - Ptl S rsy(t) occurs with
probability no smaller than 1 - 2/1220 where parameter a >> O controls the required probability.
Proposition 1 (Confidence Radius). The confidence radius Tag Tzz(() (L) in Desinition 2 is determined by
(t)(t)= EoeBr( 12 11 (N (N),0,))
a llog(t)
(11)
EbEB (2116
1)2
where log(t) is of natural base.
3) Algorithm Details: We now present the bias-sensitive UCB algorithm. The pseudocode is provided in Algorithm[]]r Appendix [ The algorithm iterates for T rounds or until convergence. At the beginning of each time slot f, the agent updates P.y (t-1) using (10) and riy (t-1) using (11). Then, computes the upper confidence bound estimation of probability Piy:
(C = [i,, (t 1) + ray (t- 1)]
(12)
where []] A minf. UCB). With this operator [[]_ the agent tends randomly explore if all arms under-explored. We set UCB = 1 in the experiments (13) In (1)) if Pry - 1) is larger than 1/2, then arm is likely to outperform arm j based on the historical observation, indicating a higher
'The term "bias" in "unbiased estimator" differs from that in "bias of evaluator". "Unbiased estimator" implies that the expected value of the estimator equals the true value being estimated.
5

---

reward through exploiting model i. If rty It 1) is larger, then the uncertainty regarding arms and higher, indicating stronger need to compare arms and j in the following time slot.
After that, the agents computes the UCB estimation of Borda score:
UCB.(t) K-I Ejeryo (CB
(13)
Finally, the agent selects the two arms (t) and x2(() with the maximum values of (CB
max=(1) (C) (1) + UCB (21))
(14)
Different from some existing works (e.g., I1 in dueling bandits that choose the best arm (e.g.. with the highest UCB) and its "strongest competitor", our algorithm chooses the best and second best arms (e.g., with the highest and second highest UCB values) for analytical simplicity. In Appendix E we empirically show that replacing the second arm with the "strongest competitor" may degrade the performance, especially when the number of arms is large or when a Condorcet winner does not exist.
3.2 Regret Analysis
We now bound the round-average regret of the proposed algorithm. The proof is given in Appendix F The proof path follows [T3], while it more difficult due to the complex form of the estimator and confidence radius. Note that essentially derive the bound for average regret. This bound is also applicable to weak regret by relaxing it to average regret in the proof (see Appendix
Theorem (Regret of Bias-Sensitive UCB Algorithm). The bias-sensitive UCB algorithm with T rounds has round-average regret of
UCB (K(K- - 2H)
Reg (()) T
T
2UCB / (T)
H + B² log BT
2BK 1
V K-1 VT
(15)
T
where H = -E= t-20, and EbEB,, - 1)2/
According to Theorem
[ we can determine the order of the round- regret and its sublinearity.
Corollary (Sublinear Regret). The round-average regret of Algorithm sublinear with an order of
B ( (oog(())//T))
This sublinearity result consistent with and generalizes those existing works on dueling bandits without considering evaluators' bias (e.g.. (13) Importantly, I reflects the average deviation of the evaluators from spammers. When I is larger (i.e., evaluators tend to reveal feedback either matching or opposing the goound-truth), the round round-average regret is smaller.
Unknown Bias Case
We now solve the case where evaluators' bias unknown to the agent, and the bias of any evaluator Tm belongs infinite set [0, 1]. Our approach be extended to the scenario with finite set of bias by projecting the continuous estimated bias to discrete space. Since the set of evaluators finite, their bias comprises a finite set & {711 72: ..., 7as Let N (t) denote the number of feedback sent by evaluator m and claiming 0; >mm Oj. Let (t, C M, which can be interpreted as the set of evaluators such that N (t) + N7 (t) > 0 for each pair of arms i and Let (t) denote the
set of (i. j) pairs such that Nop (t) + No (t) 0 for each E M.
Designing the extended bias-sensitive algorithm is highly non-trivial. This because the estimation of the arm performance and evaluation bias is highly coupled. In the following, we first present the estimators arm performance and evaluators' bias. Then, we propose the extended bias-sensitive algorithm that overcomes the aforementioned challenges. Finally, analyze its regret.

---

4.1 Arm Performance and Bias Estimation
Let Piş(1) and im (1) denote the estimation of Pig and tm given our estimator, respectively. After time slot I, the pairwise winning probability Pej in (I is estimated using the same estimator as in Lemma [ while replacing the ground-truth 7/o with the estimated fm (4), i.e.,
(t)(t) EmEM, (c) Po (t)-(1-))))) (1- (t))) (20 (t) (t)-1)
(16)
Lm) (2 (t) - 1)2
Based on a similar idea as estimating the arm performance in Section 3.1 we formulate the problem for estimating the bias of evaluator E .M:
1 3110m + 1 + 2 1117 Am 12 2
fm = arg min
(17)
2
In the first term, Um = (1 - 1, E [m)))). and bddh = (1 -t)((((() (t)- (t).j E Im (1)) where (t) e (t) + (t)). It aims to find the best 1) that minimizes the estimation error of bias given the recent (t), similar that in (9) The second term introduced for the algorithm to be proposed. Its goal is to restrict the gap between the previous estimation 7i, and the new estimation, where y balances the two terms. Solving (17) via the KKT conditions yields the estimator.
Lemma 2 (Bias Estimator). After time slot t, the bias of evaluator 4m in 33 is estimated by (1) (20:) 1) (1) (1) 1) + 7mm
fm = EijeJ
(18)
Ei.e,...,, (26:) 1) +7
Estimators (T)) and [18 form system of equations, and solving them jointly yields Prg (1) and (t). However, Pty(t) and fm (t) are highly coupled. i.e., the performance estimates depend on the bias estimates and vice versa, and the joint estimation problem non-convex. Although is possible to let (t)(t) and fm (t) update iteratively using (T6) and (18) parameter (t) usually converges to local optimal solution Pig (t) 0.5 due to the non-convexity. To address this, we decouple the evaluation bias from the arm performance estimation when initializing the estimation in each time slot and propose a BCD-based algorithm [23
4.2 Extended Bias-Sensitive UCB Algorithm
We present the extended bias-sensitive UCB algorithm. Its pseudocode is given in Algorithm of Appendix G At the beginning of time slot f, estimators (t - 1) and fm (t 1) are computed. Specifically, estimator (t ( 1) is first set to P. (t (fc-1) 1) A N (t (05-1)//6 ()/ i.e., the estimation of arm performance ignoring the evaluators' bias. This process decouples the impact of evaluators' bias estimation and that of inaccurate performance and bias estimation in the past time slots. Based on this p.j (t - 1), estimator 7m (t. - 1) is computed using (T8). Then, according to BCD [23), (ty 1) and (t - 1) are updated in sequence twice. We empirically show in Appendix K.7 that performing such updates twice leads to the best performance Either increasing or decreasing the rounds of updates leads to regret increase.
sy (t 1) + NT 1)),
After that, the agent estimates the confidence radius ítz(l - 1) with the estimated bias fm - 1):
logit-1) 1) Pl 11- 1)= EmeMi,(0) 12 (1 1) 1/ (NT) DHN 1)J
(19)
EmeM (2mm (t 1) 1)2
Note that this is not the actual confidence radius for the estimators and thus leads to additional regret in decision making (see Section 4.3). Finally, P.s (t - 1) and Fty (t 1) are substituted into B to compute (t), and the arms that optimize problem (1) are selected.
Note that these steps on the initialization and first update of p.y (t 1) and f.. - 1) each time slot are used to stabilize the estimation and can be skipped after a certain number of time slots once the estimation is relatively accurate for convergence acceleration. We empirically find that such a time slot threshold can be set in the form of cK log K, where e is tunable coefficient.
7

---

4.3 Regret Analysis
We first quantify the actual confidence radius under estimators in (16) and 18 able to bound the regret of Algorithm 2
with which we are
The proof is given in Appendix H
Lemma (Confidence Radius). Given the estimators in (16) and (18). the confidence radius is
(t) EmeMitte) (ij (t)/(c)))))) (t)
E EmeMa())
(0m [c,((]]
a log(t)
Nay + (T)
(20)
Eme (2fmm)))))))) (2 - -1}2
EmeM. (2 (1) 1)2
where (t) - (t) - (1 -1-110 7m (2m))/22m 1). (t) & (p - (1-1)) - (1-mm(t)))/(2ffmm en (t) (27m - 1)
Quantifying the regret using the difference between (t)(t) and r is challenging, because the mapping from the confidence radius the exact probability an estimation falls within the radius can hardly be solved, due to the complex form of estimators. Thus, we define a parameter {(t).
Definition 3 (Parameter {(t)). For each time slot t, let E(t) denote the minimum non-negative value such that E(t) 2 1/2 (HF (P (10t, (t) Puyl S ri (t)( - P (1px, Payl (t)())) where HF(-) is the tight lower bound of (1)) Pill r (t))
As will be seen in Theorem 2. lower E(t) leads a lower regret. There various cases that ensure <(t) = 0. Although it is hard to derive all the cases due to the complex form of Fiy (t) and ri (t), we list two examples: (i) Pay (t) ri (t): (ii) Mm (t) = 1 and fm (t) E (0.5, 1] for all m E M.
Then, the round-average regret can be determined, with the proof given in Appendix Theorem (Regret of Extended Bias-Sensitive Algorithm). Under Defimition 3 the extended bias-
sensitive UCB algorithm based on estimators in (T6) and (18) has a round-averase regret of
UCB K(K 1) 2 H + Ei= s(t)))
Reg(2(t)) S
2UCB log(T)
H + B² log 20)
2BK 1 K-1 VT)
(21)
T
When compared with Theorem [ for known bias case, the round-average regret under unknown bias case has the same order but incorporates an additional bounded error related to {(t). If g(t) is monotonically decreasing and converges to zero as -> co, then this bounded error approaches zero. However, due to the non-convexity of the joint estimation problem, proving this convergence is an open problem under BCD. In Appendix [ we empirically show that this bounded error is small and can approach zero.
5 Experiments
We consider that the user bias follows Beta distribution Beta Bn) 21). We use the BT model where is coef-
to model the winning probability of arms (21), i.e., Pij e 2*//(e- (e + te)))
ficient associated with arm i following Gaussian distribution N N(,, o²) and Condorcet winner typically exists under this model. Unless otherwise specified, we set 7mm Beta(ag 2, Bg = 1) and N(p = 0. 2). Through empirical tests, we set
ax a0(E (27mm
1)²)%/(Em 121jm= - 1))2 where on = 0.51 [1] and T/m can the recent estimated value for unknown bias case. The term a relies on the recent estimation of Tm and helps to mitigate the over-exploration due to the presence of evaluators' bias. We set coefficient = 50. Our code is built based on open source code 28) for dueling bandits. Experiments are conducted on a compute platform with AMD Ryzen? 7 7800X3D (8-core) processor and 64 GB of RAM (4800 MHz). We run each experiment for 100 times and show the average results in this section. The results with standard error be found in Appendix K
We compare our algorithms with five baselines in dueling bandits: Relative Confidence (denoted by "RC") [10], Relative UCB (denoted by "RUCB") Bayesian method Double Thompson

---

Cumulative Average Regret (4)
Cumulative Weak Regret (L)
Arm Heter. o²
Bias Concentr. On
Arm Heter. o²
Bias Concentr. Qgg
1.0
2.0
4.0
1.0
2.0
3.0
1.0
2.0
4.0
1.0
2.0
3.0
RC
1374
1338
967
2845
1338
687
596
525
502
1847
525
278
RUCB
1906
2134
1154
2832
2134
1185
1018
1144
719
1829
1144
506
DT
1396
1425
942
2621
1425
640
445
492
375
1428
492
191
MBTW
1220
1509
726
1769
1509
1448
175
162
140
569
162
92
UCB
1283
1426
732
2581
1426
706
553
548
336
1583
548
153
RC-B(*)
1378
1611
1050
2207
1611
803
649
869
727
1119
869
502
RUCB-B(*)
993
1120
709
1191
1120
1055
422
480
370
604
480
446
D*-B((*)
430
411
344
631
411
280
198
210
168
436
210
110
*S-UN(*)
690
689
387
825.
689
637.
194
161
94
340
161
92
BS-K(*)
654
7.3.
407.
554
713
624
116
90
79
60
90
82
Table 1: Performance under diverse arm heterogeneity (denoted by "heter.") and bias concentration (denoted by "concentr.") with 10 arms and 10 evaluators. Our methods are marked with "(*)". The best, second, and third best results are marked bold, underline, and dashed underline, respectively.
(denoted by "DT"" [12]. Modified Beat The Winner (denoted by "MBTW") [27], UCB (which follows [13] but omits the cost constraint). Meanwhile, we incorporate our sensitsee estimation in 2 and obtain bias-sensitive versions of RC, RUCB, and DT (see Appendix K.Tp. They are denoted by "[Baseline Name]-B". Our Algorithms and 2 are denoted by BS-K and BS-UN for known and unknown bias cases, respectively. We use "(*) to mark our methods (including the bias-sensitive versions of baselines and our proposed BS-K and BS-UN), Experiments are conducted under unknown bias case, expect for those of BS-K. We show the cumulative regret Σ (eg(a(()) because (i) the values of round-average regret are very small, and (ii) cumulative regret can infer marginal regret in figures. In Table [ the round-average regret can be obtained by dividing the cumulative regret by T = 10000.
Algorithm
Algorithm Comparison: Tables and show the cumulative regret after 10000 rounds. The algorithm convergence and standard error are shown in Appendix K.2 The numerical bias estimation error can be found in Appendix K. We have the following observations. (i) Our proposed BS-UN and BS-K algorithms achieve superior performance under both average and weak regrets, ranked top three among all algorithms for most cases. When compared with RC, RUCB, DT, MBTW, and UCB, the average regret reduction of BS-UN can be up to 71.0%. 70.9%, 68.5%, 56.0%, and 68.0% 68.0%, respectively; the weak regret reduction of BS-UN respectively. (ii) The bias-sensitive versions of baselines usually achieve lower regret than their original versions, showing the effectiveness of estimators. For RUCB and DT, their average regret reduction can be up to 58.0% and 75.9%, respectively; their weak regret reduction can be up to 67.0% and 69.5%, 5%, respectively.
be up 81.6%, 86.9%, 76.2%, 40.2%, 78.5%.
Impact of Og:: Our BS-K and BS-UN algorithms are more beneficial when bias concentration Og is lower. Specifically, smaller ag implies a higher degree of evaluators' bias. In Table [ when ag reduces from 3.0 to 2.0, the average and weak regrets of baselines increase by up to 1.23 times and 2.58 times, respectively. However, the average and weak regret increasing are 0.08 and 0.75 for BS-UN and 0. 14 and 0.09 for BS-K, respectively.
Impact of o² A larger o² implies a higher degree of arm heterogeneity. Since the evaluators' bias is not accounted by the baselines, a larger heterogeneity makes it casier to identify the best arm and hence lower regret. As the evaluators' bias is accounted by our methods, moderate heterogeneity can be sufficient for identifying the best arm and reducing the regrets.
Impact of Evaluators and Arms: From Table 2 (i) our methods are not sensitive to the number of evaluators. As the number of evaluators increases from to 20, the average and weak regrets of our BS-UN increase by -0.10 and -0.35 times, respectively; those of our BS-K increase by 0.08 and 0.32 times, respectively. (ii) The increasing in the number of arms increases the regrets of our methods. This is acceptable, because in the I.L. evaluation example, the number of users (i.e., evaluators) always large, while the number of L.MMs (i.e., arms) is usually small, e.g., around 10. We further evaluate large-scale settings with 100 evaluators and 100 arms in Appendix K.4

---

Cum. Average Regret (J)
Cum. Weak Regret (1)
Method
Num. of Eval.
Num. of Arms
Num. of Eval.
Num. of Arms
15
20
5
15
20
5
15
20
15
20
RC
1590
1142
1301
561
2250
2568
689
409
497
85
1303
1626
RUCB
2293
1924
2042
813
2277
2499
1272
979
1067
181
1356
1593
DT
1548
1073
1221
695
1854
2006
491
295
349
142
702
802
MBTW
1444
1452
1509
1218
1260
1330
177
124
182
48
307
438
UCB
1604
1099
1252
631
1752
2115
709
387
491
77
971
1264
RC-B(*)
1801
1370
1694
575
2301
2707
934
785
1005
198
1492
1993
RUCB-B(*)
964
1102
1115
820
1360
1868
392
468
483
243
707
1146
DT-B(*))
360
375
344
169
736
1156
177
165
169
77
308
578
BS-UN(*)
68X
722
621
626
929
115.7
121
97
79
108
364
543
BS-K(*)
588
600
638
469
881
1021
57
73
75
21
306
420
Table 2: Impact of the number of evaluators (denoted by "Eval.") and arms. Unless specified in the column title, the default number of arms and evaluators 10. Our methods are marked with "(*)".
Ablation Study: When compared with the alternative estimator given in Appendix A our arm performance estimators (10) and (I6) reduce the average regret by 58.3% and 42.1 and weak regret by 78.1% and 61.6% for known and unknown bias cases, respectively. When compared with other estimators (e.g., estimators based on conditional probability expression and other estimator update procedures), our bias estimators in (18) reduces the average and weak regrets by 11.2% 49.17 % and 13.1% 75.5%, respectively. Please refer Appendix K.6 details.
Conclusion and Limitations
This work presents the first study addressing evaluators' bias in ducling bandits. We overcome the challenge of non-convexity and bias heterogeneity and propose bias-sensitive algorithms with regret bounds. When compared with baselines, when the evaluators' bias levels are more heterogeneous. Meanwhile, our proposed estimator can be incorporated into baselines and achieve regret reduction of up to 75.9%.
algorithms reduces the regret by up to 86.9%, especially
The main limitations of this work contain four parts. First, the bias of each evaluator is modeled to be deterministic and unchanged across time. To extend the model to stochastic and diverse bias, we may learn from adversarial dueling bandits and extend the techniques from addressing time-varying winning probability to vareing bias. Second, the regret bound for BS-UN contains term (t),, which was not derived in closed form. is important to derive the specific expression of to reveal further insights, overcoming the difficulty in analyzing the performance of BCD algorithm for non non-convex problem. Third, the recent bias modeling is only evaluator-dependent. It is interesting to consider arm-dependent bias, characterizing evaluators' distinctive bias toward arms. Fourth, this work is motivated by human bias in feedback. would be beneficial to construct real-world experiments with humans for algorithm evaluation.
Acknowledgments and Disclosure of Funding
This work was supported in part by the National Natural Science Foundation of China under Grant 62202214 and Guangdong Basic and Applied Basic Research Foundation under Grant 2023A1515012819.
References
[1] Aleksandrs Slivkins. "Introduction to Multi-Armed Bandits". In: Found. Trends Mach. Learn, 12.1-2 (Nov. 2019). pp. 1-286.
[2] OpenAL. GPT-4 Technical Report. https: : c/ccdn. openai com www.paperss........ Accessed: 2025-05-15. 2023.
papers/ gpt - 4. pdf
3 Moran Mizrahi et al. "State of What Art? A Call for Multi-Prompt LLM Evaluation". In: Trans. Association for Computational Linguistics 12 (2024), pp. 933-949.
10

---

[4] Adian Liusie et al. "Efficient LLM Comparative Assessment: A Product of Experts Framework for Pairwise Comparisons". In: Proc. Conference on Empirical Methods in Natural Language Processing. Nov. 2024.
[5] Yisong Yue and Thorsten Joachims. "Beat the mean bandit". In: Proc. ICML. Bellevue, Washington, USA, July 2011.
[6] Tanguy Urvoy et al. "Generic exploration and K-armed voting bandits". In: Proc. ICML. Atlanta, GA, USA, June 2013.
[7] Junpei Komiyama et al. "Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem". In: Proc. Conference on Learning Theory. Paris, France, July 2015.
[8] Arpit Agarwal, Nicholas Johnson, and Shivani Agarwal. "Choice bandits". In: Proc. NeurlPS. Vancouver, BC, Canada, Dec. 2020.
[9] Shangshang Wang et al. "Neural Constrained Combinatorial Bandits". In: Proc. IEEE Confer- ence on Computer Communications (INFOCOM). May 2023.
[10] Masrour Zoghi et al. "Relative confidence sampling for efficient on-line ranker evaluation", In: Proc. ACM International Conference Web Search and Data Mining. New York, New York, USA. Feb. 2014, pp. 73-82.
[11] Masrour Zoghi et al. "Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem". In: Proc. ICML. Bejing, China, June 2014.
[12] Huasen Wu and Xin Liu, "Double Thompson Sampling for Dueling Bandits". In: Proc. NewrIPS. Dec. 2016.
[13] Shangshang Wang and Ziyu Shao. "Green Dueling Bandits", In: Proc. IEEE International Conference on Communications (ICC). May 2023.
[14] Rohan Deb, Aadirupa Saha, and Arindam Banerjee. "Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resources". In: Proc. International Conference on Artificial Intelligence and Statistics (AISTATS). May 2024.
[15] Viktor Bengs al. "Preference-basse online learning with dueling bandits: A survey". In: J. Mach. Learn. Res. 22.1 2021).
[16] Josh Tobin. LLMOps: Deployment and Learning in Production. https /
Bullstackdeeplearming wwweaarninn.ccmmm//amaammama www.comm/m/./ 11m- woottlllooooooooooooo sttppp//pnngngiieeee 2023 1lmops/ Accessed on
Jan. 2025.
[17] Yu-Heng Hung et al. "Reward-Biased Maximum Likelihood Estimation for Linear Stochastic Bandits". " In: ArXiv (Oct. 2020). URL:
222208619
[18] Xi Liu al. "Exploration through reward biasing: reward-biased maximum likelihood estima- tion for stochastic multi-armed bandits". In: Proc. ICML. July 2020.
[19] Nadezhda Bugakova et al. "Aggregation of pairwise comparisons with reduction of biases". In:
arXiv (June 2019). URL: /https://arxii: org/ haagg/abs/1190 1906. 03711
[20] Antonio Ferrara et al. "Bias-aware ranking from pairwise comparisons". In: Data Min. Knowl. Discov. 38.4 (May 2024), pp.
ISSN: 1384-5810. Do1: 10. 00.0007/100011 024
01024-2 URL: httptt:tt/t/oooooo orgoooo///1 1111000//0011000011111111
[21] Xi Chen et al. "Pairwise ranking aggregation in a crowdsourced setting". In: Proc. ACM International Conference on Web Search and Data Mining (WSDM). Rome, Italy, Feb. 2013.
[22] Aadirupa Saha, Tomer Koren, and Yishay Mansour. "Adversarial Dueling Bandits". In: Proc.
ICML. Vol. 139. July 2021, pp. 9235-9244.
[23] Paul Tseng. "Convergence of Block Coordinate Descent Method for Nondifferentiable Minimization". In: Journal of Optimization Theory and Applications 109 (June 2021), pp. 475- 494.
[24]
Róbert Istvan Busa-Fekete, Balázs Szörényi, and Eyke Hüllermeier. "PAC Rank Elicitation through Adaptive Sampling of Stochastic Pairwise Preferences". In: Proc. AAAI July 2014. David R Cox. "The regression analysis of binary sequences", , In: Journal of the Royal Statistical Society: Series B (Merhodological) 20.2 (1958), pp. 215-232.
[25]
[26) Hasti Narimanzadeh et al. "Crowdsourcing Subjective Annotations Using Pairwise Com- parisons Reduces Bias and Error Compared to the Majority- Method", In: Proc, ACM
Hum, Comm-tC Interact. 7,CSCW2 (Oct. 2023). DOI: 10. 1145 1/45// 3610183
URL: https
//doi, , 1111/00.114//31100555

---

[27] Erol A. Peköz. Sheldon M. Ross, and Zhengyu Zhang. "DUELING BANDIT PROBLEMS".
In: Probability in the Engineering and Informational Sciences 36 (2020), pp. 264-275, URL:
www.ssiiimmoolllaaa......c httpp:///pp...ssaaiiiccccooorrrr org/ Corpus ID: 229507898
[28]
DuelPy Documentation: Examples and Writing New Algorithm. 2023. URL: https://
duelpy wrryyggillb... http:/ii///lllyeeeeeeeeeeeeeeee wxwmples..pppeeeeeeeeeee
html #wri hameel.h.mll..m
[29] Nir Ailon, Zohar Karnin, and Thorsten Joachims. "Reducing dueling bandits to cardinal bandits". In: Proc. ICML. June 2014, pp. 856-864.
[30] Aadirupa Saha. "Optimal algorithms for stochastic contextual preference bandits". In: Proc.
NeurIPS. Vol. 34. 2021. pp. 30050-30062.
[31] Barna Pásztor, Parnian Kassraie, and Andreas Krause. "Bandits with Preference Feedback:
Stackelberg Game Perspective". In: Proc. NeurlPS. Dec. 2024, pp. 11997-12034.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have summarized and discussed the main contributions and scope of this paper in the abstract and Section Introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We have discussed the limitations of this work in the second paragraph of Section 6 Conclusion and Limitations.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
12

---

The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
We have provided assumptions in the main text. We have provided complete
proofs for Lemma Proposition]] [ Theorem[] [
Lemma 3 and Theorem 2] Appendices B
and respectively. We provided one sentence to explain the proof of Lemma the main text, as the proof straightforward.
Guidelines:
The answer NA means that the paper does include theoretical results. the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We have included the settings of probability model, bias model, parameters in Section 5 Experiments. Due to the space limit, we provided the settings and explanations of baselines in Appendix K
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
13

---

reproducible, they While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have included the code in supplementary material. The experiments in this work do not rely on datasets.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
public/ Ballliicggiee///ee (CodeSuumissiioooolll..
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7/nips. cc/
httpcccpppppcccccecccc.eeel.cclc http:ppllllcceeee weciic//guiie/eeeeee wttp:///SSSSSSessiiioiii..cm ssooiioliiiiyyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have provided all parameters we used and their reference (if applicable). The experiments in this work do not involve data splits, optimizers, and training details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
14

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question:
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We have provided the standard error of the experimental results in this work. They are provided in Appendix K
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative етror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have included the information compute resources in the first paragraph of Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
This work does not have human subjects or participants and data-related
concerns.
15

---

Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We have discussed the society impacts in Appendix
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g.. deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper does not pose such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
16

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We used an open source code 28 as the framework for conducting experiments. This open source code was released GitHub with MIT License. We have cited it.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithhheooo thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We have included instruction for the code in supplementary material.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
17

---

15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
18

---

Appendix A An Alternative Estimator
It is possible to derive an alternative unbiased estimator by directly substituting (1) (1) (t) + (t) P for 7/m 1/ into 4.. This leads the following estimator:
-
Definition 4 (An Alternative Estimator). After time slot t, we propose to approximate Pij in using
-17))
NO 2m -1
Pt)(t) = [B))(t] bEB
(22)
Although prove that this alternative estimator is unbiased, this estimator (t) approaches infinite when there exist evaluators that are spammers, i.c., when there exists E B such that % = 0.5. This is not practical,
cannot prevent the existence of spammers in practical systems.
Formally, under this estimator in Definition the confidence radius and the associated round-average regret (i.e., the regret under our proposed bias-sensitive algorithm while replacing the estimator and confidence radius accordingly) can be determined as follows. The proofs are similar as those in the main context and hence omitted here.
Lemma 4 (Confidence Radius under the Altemative Estimator). The confidence radius (ty in Definition determined by
a log(t) (NN NJ (t)) 1|
Tey (t)
Σ
(23)
[t)
(EB,,(t-1)
Lemma 5 (Regret under the Alternative Estimator). The bias-sensitive UCB algorithm under the estimator in Desinition 4 and confidence radius in Lemma has a round-average regret of
K-1
(K
1)K
Reg 2 (1) 5
(1 UCB)
H(1 + KUCB)
T
2
(K 1)KUCB / log(T)
(1-
1
H B
2 1
+1
1
+
(24)
r
B
T
TB
T
where r minses 12 1.
When comparing with the round-average regret of our proposed bias-sensitive algorithm in Theorem this regret is different in terms of I. As we can expect, if there exists any evaluator that is spammer (i.e., 1/ = 0.5), then I't is equal to zero, making the round-average regret approaches infinite.
I
Appendix B Proof for Lemma
By substitute (10) into B(), we have
Nº (t) Nà Nz)+
EveBy (2 1)
- (1 m/6
El),(())
(25)
EneB, (2mg) - 1)²
Since event >m o₂ for any t' < t is a Bernoulli trial which holds with probability Pr(o; Xm 0,)- E (O/(N) (1) + No =Pr)= Pr(o:
Am 0j) for any ensuring 7mm .n. By substituting 4 into
25 we have ((), Pij.
Appendix C Proof for Proposition I
To alleviate the coupling of the randomness among time slots, we introduce x table. Cell (b E B, E T) corresponds to the s-th times that { is selected for evaluators of bias b. Let
19

---

N denote the number of time slots t' (i) until (i.e., on and before) the s-th times that {i.}} is selected for the evaluators with bias ng such that (ii) evaluator m sends feedback with or Fm Oj- and (iii) m vig Let Pij denote the fraction of feedback sent by the evaluators of bias b claiming of mm Oj among the first times that { j3 selected for the evaluators of bias b. That is,
bbs by
h.8 Vi
(26)
Then, according to Hoeffding Inequality, for any > O.
1 a log(t)
9ij
Blq.j"
2
(27)
22a
where "1 denotes the expected value of considering the randomness of evaluator feedback. According to E biel can be determined by
9ú) b.
El
6. = Pi5 + (1 -
- (1-)(-
(28)
Substituting 28 into the inequality the left-hand side of 27 have
a log(t)
(ntpis + (1 - mh (1 - Pty) ))
(29)
Multiplying both sides by 120g 1| and substituting 26) inequality
29 can be transformed into
(
No
1/1 a log(t)
(1 766) (2n) 1) - -P:y(2n 1)²
12m
(30)
Let No. (t) + No. (t) and hence N = N (t). Based on triangle inequality, considering (30 for all possible b (t) the following inequality holds:
Pr
Σ
NO N3(0)) (1- (1-18)) (2n6 - 1) Σ
Pig (21)
1)²
(t)
bEB,,(t)
log(t)
2 2
12
1
2
(31)
(1)
N).
(E
Finally, dividing both sides of the inequality in Pr(-) by EbeB. defined in (11) is the confidence radius given the definition of p.g
12mh - 1 we show that (t)(t)
Appendix D Bias-Sensitive UCB Algorithm
Algorithm shows the pseudocode of our proposed bias-sensitive UCB Algorithm.
Algorithm Bias-Sensitive UCB Algorithm
1: for each time slot f. = to T do
2: Update (ty using (10) and r.y (ty (t-1) using (T):
3: Estimate (C) using (13) for E K;;
4: Select the arms x (t) and x2 (f) that optimize problem 14):
5: end for
Appendix E An Alternative Algorithm that Selects the "Best Competitor"
In our algorithm, in each time slot I, the agent selects the arms with the highest and second highest UCB values as the first arm (denoted by 21 (f) and the second arm (denoted by (2)))), respectively, ie.. (t) arg maxix (t) and 22()) arg (ax UCB,(t). As alternative,
20

---

Table 3: Methods considered for comparing the selection of the second arm.
First Arm
Second Arm
Arm/Bias Estimation
RUCB-B
Randomly pick from an
"Strongest competitor"
RUCB-B/Our
optimistic arm pool
DS-K-Modified
Highest UCB
"Strongest competitor"
Our/Known Bias
BS-K
Highest UCB
Second highest UCB
Our/Known Bias
BS-UN-Modified
Highest UCB
"Strongest competitor"
Our/Our
BS-UN
Highest UCB
Second highest UCB
Our/Our
Table 4: Comparison of the selection of the second arm under BT Model. Different columns
correspond to different number of arms.
Cumulative Average Regret
Cumulative Weak Regret
10
20
30
50
10
20
30
50
RUCB-B
1943
2914
4280
8990
685
1444
2451
6468
BS-Modiffed-K
756
1308
1592
5155
59
322
644
1732
BS-K
868
1361
1748
4440
57
336
537
1256
BS-Modified-UN
829
1469
1951
5643
96
418
815
2291
BS-UN
990
1461
1834
4109
92
477
687
1355
the agent may choose the "strongest competitor" of the first arm as the second arm, i.e., r2(()) (e) (t). In the following, we empirically show that for the second arm, arg max;ex) (x. UaB
considering the second best arm (i.e., the one with the second highest UCB) and the "strongest competitor" of the first arm achieve similar performance for many of the cases, while the former can achieve better performance when the number of arms is large or a Condorcet winner does not exist.
To conduct such experiments, we compare five methods as shown in Table 3 Specifically, RUCB-B built upon Relative UCB (IT] while incorporating our bias estimation method. K-Modiiiie and UN-Modifieed correspond to the methods choosing the "strongest competitor" of the first arm as the second arm, incorporated with our arm and bias estimation methods. BS-K and BS-UN are our proposed approaches.
shows the results under the same arm performance modeling the main experimental results, i.c., where BT model is considered. In this case, a Condorcet winner always exists. First, for many of the cases, BS-K-Modified and BS-K (as well BS-UN-Modified and BS-UN) achieve similar average and weak regrets. This indicates that those two methods for choosing the second arm do not make significance difference. Second, when there are 50 arms, our BS-K K and BS-UN always outperform BS-K K-Modified and BS-UN-Modified respectively. This implies that independently selecting two arms (rather than having the selection of the second arm rely on the first arm) for exploration is more beneficial for arm performance estimation when the number of arms is large.
Bradley-Teree Terry (BT) Model: Table shows
The arm performance matrix initialized with the BT model. To remove the Condorcet winner, for each arm, we randomly select arms that are initially weaker than this arm and increase their winning probabilities (that beat this arm) to a random value within range (0.5, 0.6). In Table when Condorect winner does exist, our BS-K and BS-UN always outperform BS-K K-Modified and BS-UN-Modifien in terms of the average regret, respectively. In this case, the "strongest competitor" of the first arm may perform badly when compared with other arms, so selecting the "strongest competitor" as the second arm may lead to a high regret and hence increase the average rerget. RUCB-B achieves the worst performance. This result shows that the choice of the first arm makes more significant impact than that of the second arm.
Non-Existence of a Condorcet Winner:
Appendix F Proof for Theorem i
We first present the proof details. Then, we prove auxiliary inequality used in the proof.
21

---

Table 5: Comparison of the selection of the second arm under non non-existence of Condorcet winner. Different columns correspond to different number of arms.
Cumulative Average Regret
Cumulative
Weak Regret
10
20
30
50
10
20
30
50
RUCB-B
3619
3966
4918
8619
1133
1913
2841
6238
BS-Modified-K
2602
2387
2625
5205
224
476
865
2297
BS-K
1715
1787
2146
4737
198
588
755
1631
BS-Modified-UN
2742
2701
2808
5418
276
811
990
2661
BS-UN
1401
1768
2186
4648
437
697
907
1960
F1 Proof Details
This proof essentially derives the bound for average regret, while it works for weak regret by relaxing the weak regret to average regret in inequality (a) of (33)
Based on the definition of average regret RegA (x))).
T
Σ (a)))a(())=))))))))))){))))))( = B - (0z.(e) 0x2(t)/22]
(32)
We define I(l) - (1), x2)) the of arms that are selected in time slot L. We determine the
upper bound as follows:
8-- - (0m)(1) + 0ma(t))/2
0,- - EiETio 01t EiE(()) 2
1 EiEr(o (UCB,(t) 0,) 0,- UCB,-
(33)
k-T EiEr()) Ejjt UCB, (t)
R Ejjt Pany UCB,-UC,,,
2
Inequality (a) holds because arm E I(t) is selected by the algorithm and hence UCB, UCB:- (t) 2 O. Note that if weak regret is considered, we can relax the weak regret to average regret using (t) (z)( 2 ΣvErt) 0,/ in (a). Inequality (b) holds by rearranging the terms. Inequality (c) holds based on the definition of 0, in (2) and (CB,(t) in (33). Let (t) e EieT()) Ejfs (UCB,,() P2)/2 and let 22(() & Ej (pe-) UCB r (()) Thus,
Σ 0r- (Omi() + 6 (1)(1))
S
K (()
1
Σ
2
Σ (t)). (34)
K
In the following, we will bound the above two terms
E ( and ΣT= B[)2(()), respectively,
Bound DT_ E (t)]: At the beginning of Algorithm each ducling pair will be selected once. This holds because at the beginning of the algorithm, the arms have not been explored such that that UCBs cannot been computed, so their UCBs' are initially set to be large values to enable the exploration. This is consistent with existing works [1] [3) These selections of each dueling pair take a total of to = C(K, 2) rounds. Thus, the regret during rounds to to is given as follows:
[(),(()) < (K 11)CCBO
(355)
where UCB the upper limit of (C),,()) for for N.
Then, we focus on the rounds after to. i.e., t = {to + 1,..., T}. During these rounds, we define the following events for models and j:
(t): (t)(t) Pij > Tt (t);
22

---

(t): complement of (t).
In particular, event En (t) corresponds the case where Psy (t) has been overestimated and exceeds the upper confidence bound. This case induces UCB (t) 2 Po- When event (t) happens,
(t) - Pij - (t). Thus, we can bound Ei= 1 (t) as follows:
T Σ tmtg+1
T
UCB (() 1(UCB 2 pbj)
E
Σ t=to=1 LiEZ(()J
(36)
2
where 1(.) is the indicator function, i.e. 1(x > y) 0 y, and 1(x y) 0 otherwise. Since exactly one of events (t) and (t) happens,
UCB 15 (1) Pij 1 (UCB:,,(1) 2 Ptj) p())
E
2
(EI(()
UCB -Pj (UCC
=B
2
iEZ
B(#1.((0)
UCB:,(t)-PM Psj
(U)CB,(()2P,))((EE)
2
(ET(1) FAI
(37)
Substituting 37
into (6).
T S Σ (() + Σ ([
Σ
(1)
(38)
fo++1
We now bound these two terms Σ Ei= 1 (f) and Ex= 1 [t)) respectively.
Bound ΣT
+1= +1
T
E[)r,1(t)]:
Since event (t) implies UCB:y(t) 2 Pij. we have
Σ -
E
1
(1)
E
(EI(()) Ejji LCB,, P1 (E) (1)
to+1
t1 IE
E
ΣiET()) Ejjs PlE,, 2
UCB
(T)t)
(39)
+1
E
E
Σ ΣiEZ())
Ejjs 12a
UCB
2 [0
(K - 1)UCB >i
2aa
Inequality (d) holds due Definition 2 and Proposition
Bound 1 2(21.2(t) It is straightforward that Ei B[2).2()) According to the definition of event (t), we have
BE 212((t)
Σt 11,((1)
Dt EiEZ(O) Ejer Fig (I)UB
(40)
Valog(T) Dd (t))CBB
where Z(t) is equal to
Σ3Σ
2n
(41)
(EZ(() BI (2 1)2 (N) N2 (N)())))33))
23

---

Inequality (e) holds because event (t) implies UCB,y(t) - Pij S 2ry(())
Let r
-
EvEB, (2n (t)) We now have > Eimro+ (()):
T
T
1( (())222 -1
Σ t=
Z(t)
ΣE
Σ
(42)
(t)
(N + (t)
t iEK jæi
bE
In Appendix F2
we prove that the upper bound of Σ 21= [[Z is given as follows:
2(K -
2(K - 1) B² log (BT2a) 2B
Σ
B[Z((]
r H
VK(K-
(43)
r
t=to+1
where H
By substituting
43 into 40)
2(K - 1)UCB a (T)
2BKT
E
Σ
112(t)
H + B log ( +
(44)
r
K
1=
To sum up, by substituting (35
339 and 44
determine the bound of Σ B[+((()):
T
B (t) < UCB (to + H
K -
=
2UCB CaCB/alog(2
12BTT
H B² log log(B72g +
(45)
K K-11
Bound Σx1 E (1)]: According to the definition of (2))), we can determine the following
inequality:
pr- - UCB:,,(tt) 1(pr 2 (CB;,;()))
(2(()
S
(46)
2
jf
Hence, considering the iteration before and after to rounds.
E
(t))
i 1 Ej
UCB
LCB
(47)
p
K
UCBt-
UCB Et=l++1
Substituting
(45) and 447 completes the proof.
F.2
Upper Bound of 1i= B[Z(t)]
We now derive the bound of ΣT
Ei= B[Z(t)] Recall that
T
1 I(1))22% 1 (1) N),(t)
Z(t) = Σ
(48)
t=t++1 iEK juti (t) (L
1=
The evaluation selection frequency (1)(() A (n (())EE satisfies the total frequency constraint
EiER (t) (t). Recall that B [B]. Define the event
(N, & there exists b E B s.t. mi
N
N Nlog BB
2 and Σnly N J. (49)
B
BEB
and let (i,(NO, () be its complement. Since we suppose ni²(() follows the uniform multinominal distribution with total selection number of (t), n², (t) follows the binominal distribution with probability 1/B. Applying Hoeffding Inequality, this leads to
2ca
Pr(n (( -)) S exp(
(50)
(,,
24

---

for any b E B and for any > O. By taking (Nr(( log 3/2n)/2 we obtain
Pr P (t), 1)) & B log( B{²a)) S 2a.
(51)
Recall that (t) = N (t). Thus,
Σ Z(t)
Σ
T
1 (t),,, + (N,)())
Σ
1 E I(T)) 2n
1
F|B
(2)
t= iEK iti
BE
T
1 (
Σ
ΣE
r
1= -IEK |EE jzi
Σl 11 21(1)
1 (X; (N,())
Σ
r|
t= jfi
BE (0)
Σ Ei Zz(t)
(52)
For the first item on DT t1+1 t0 Zi((),
Σ E [Z) = Σ
Σ
t=
1- Kj
(53)
2(K - 1)
2a
t=
For the second item on Eizto+1 (1),, we define m()) - B² log (laa). For n 2 m((), we have
n B
logoo (B
n 2B
2 1. Then, we can conclude that
Σ
72(1)
2 r
Σ
E
(n T))
Biy BEB,,
(n)
t=
(T)
2
I(I)((
Σ S(n
(54)
(T)
2
1(1 E(EE((t))
m(T +
Σ
f(n, T)
r
==m(()
(Ty(T)
2
Σ
1(i E B(t)) log( 2T +
Σ
f(n,T)
KJ
n=
where (n) the number of times that evaluators with bias b participate among these n selections. Meanwhile, f(n, t) for n 2 defined as follows:
1
1
f(a,t)
max
(x.)
R
B
V
B
S.L.
Tj = n1
(55)
1=1
n log Biaaa
3;
iE....., B.
B
2
11, ..., min [B]]
25

---

We define an auxiliary function g(n,t, t, B) as follows:
B 1
g B)
max ( R.n)
B
iml
(56)
s.t.
2i n
n1 log( Bt
24 2 B
ie ,,..., B.
2
It is easy to show that f(n,t) t) g(n t, min(n, B)) S g(n, t, B) S V
2B
This leads to
(T)
N.
Σ
f(n,t) 22B
Σ
$ 2BN,,
(57)
Vn
(t)
Hence,
(T) Σ
2 Σ S
(z(()=
1(i E I(() 1 log (BT2a) + +12BNi;(TT)
r ijj
x
2(K - 1)
B² log 2T + 2v
K(K 11) Σ Nij(T)
(58)
r
2(K 1)
B² log (72a) + 2v2B
KKK 1IT.
r
Combining (t) and Z2(t), we get
T
< 2(K 1)
2(K -1) H
2/2B V VK(K 1IT, (59)
Σ B[Z(t)]
B² log BT +
r
(1
where H Ei 21
22a
Appendix G Extended Bias-Sensitive UCB Algorithm
Algorithm 2 presents the extended bias-sensitive UCB algorithm for unknown bias case.
Algorithm Extended Bias-Sensitive UCB Algorithm
1: for each time slot t = 1 to T do
2: Set P.y (t 1) = p. (t 1), compute îm (t 1) using [T]]
3: Repeat twice
4: Update pty(t 1) using 16 update îm (t 1) using (8)
5: Compute (t 1) using 19
6: Substitute (ty(t - 1) and Fig ( 1) into 12 and 13 to compute iC,
7: Select the arms 21 (L) and xa (1) that optimize problem (14;
8: end for
As we mentioned in the main context, line 2 and the first update of Pij 1) and (t 1) in line 4 can be skipped after certain number of time slots once the estimation tends be relatively accurate to accelerate the convergence. We empirically find that this time slot threshold can be set in the form of cK log K. We set = 50 experiments. The explanation of the twice update lines 3-4 can be found in Appendix K.7
26

---

Appendix H Proof for Lemma 3
The proof path is similar as that for Proposition To alleviate the coupling of the randomness among requests, we introduce a M x t table. Cell (m E M, E 7) corresponds to the s-th times that {i.j} selected for evaluator m. Let Nij denote the number of time slots (i) until (i.e., on and before) the s-th times that {i,j} selected for evaluator m and (ii) evaluator m sends a feedback with 7m Oj. Let Ti5 m.s denote the fraction of feedback sent by evaluator m claiming o; >m Oj
among the first times that {i,j} is selected for that evaluator. That is,
2 Ej
Pij
(60)
8
Then, according to Hoeffding Inequality, for any > O,
a log(()
2 [2a
Pr
m.s Mij
m. "1 S Elggy
2 1
(61)
where Elg.j m. denotes the expected value of
9iz m.s considering the randomness of feedback due to
arm winning probability and evaluator bias. According to (4) ElT.j can be determined by
Blg ml = Pip + (1 7m (1 PPy)-
(62)
Substituting 62 into the inequality on the left-hand side of (61. we have
log(t))
m. T
(1mpis + +1 - 71 p(y) $
(63)
5
Then, multiplying both sides by 12 (t) - 1/, the following inequality holds for all m E M and E T:
(NT) /s- -1 (1- mm)) (2 (1) -1 11-1))-222 (2 - (2 11-111)2 1),pp S 22 (1) - 1/ / a log(!) (64)
NN (1) NJT (1) and hence No sj (t). Then, we reorganize the inequality expression inside function Pr(-). By extracting e7 (t) (2mm 1)/(2 (t) 1) at the left-hand side of
Let s =
the inequality and substituting o5 (t) & (N!) (t)/ (t) + NJJ (t)) - (1 7m)) 1) and
8. (t) (N (1) + (()) (1 fm (t)) - 1), we have the following:
2 (1) Oz (1) Ptg P.g (2m (1) 1)² (07 (<), (1)) - ,े (1) < 22 (1) 100-1111 1/y log(t)
(65)
By triangle inequality and rearranging the inequality expression, we can obtain the following inequal- ity:
(2m (t) 1 (t)
log(t) (t) + NT)
(g7() Pij (2) (1) < (0)
1)²
(66)
Based on triangle inequality, considering (66) for all possible m E MMa((t), the following inequality holds:
()) (1) (T) (1 (mm((t)))) (2 (t) (1)
Pr
Σ
Σ
Pij (2mm 1)²
(t
mEM,; (t)
12 (t)
a log(t)
( (1)(((())))
Σ
> 1- 120"
107 (1)
(1)+ N
(t
(L
(67)
Dividing both sides of the inequality in Pr(-) by factor EmeMi (2im proof.
(2fmm (t) - -1)2, we complete the
27

---

Appendix I Proof for Theorem 2
The proof path is exactly same as that in Appendix F except that the event probability P (()) in
399 and P Plp:t 2 UCB,-s (t)] in (47) are changed. Specifically, as in Appendix F for any request
to 1,... T. there are two possible events:
E (t): (t) - P.j > Fgy
(t): complement of Egy (t).
According to Definition
(t) = 1 Plld, (t) Pijl S Ps)(t)
1 (() - -iyl S rt,
+ E(t). (68)
2
2
By Lemma (())s(() Piyl < r2) (0))22 + E(I) < 1/12a + E(t) and hence (() S
1/t2a + E(t). Due to the same reason, P(p 2 ,CB;,, (t) < 1/tta + E(t). Substituting (())
339 and Plps>, 2 (C):,, (47), we complete the proof.
Appendix J Discussion on E(t)
Let A(T) -E E E(t). Proving limT- A(T) - 0 can be challenging due to the non-convex joint bias and winning probability estimation problem in (17). Instead, we provide the following evidences to show that A(T) can be small and may approach zero.
(i) - oc, we show that fm (t) + 7mm + e. Showing this result analytically is challenging. This is because due to the non-convexity, proving such performance guarantee under BCD remains an open problem. We empirically show the convergence of the bias estimation error Im (t) 7mm in Appendix K.
if (t) Tma + then we show that {(t) is non-increasing and converge to value fg. so limy- A(T) + fg. Here, <g decreases as |c| decreases, and it approaches zero if E -> 0. Specifically, recall that parameter E(t) is the minimum non-negative value such that E(t) 2 (HF (IP (Ipe((t) Pall S rry r()) IP (1):)(t) ptll S (t)). There are two possible cases: (a) (t) S (ty(t) under which {(t) = 0 always holds; (b) (t) > (ty under which E(t) > O. We can show that if fm (t) + 7m + e, then based the definition of confidence radius, the gap between ri (t) and (t) changes continuously, so the analysis can focus on case (b). Based on Hoeffding inequality and the definition of E(t).
(ii) As t
P (1) - pul S (t) 2 1 2//22a
(69)
P (1) - - ftt 1- 2/t2 + E(t).
(70)
Based on the definition of confidence radius, as (l) - 7/m + e, there exists a sequence d()
such that (t; (t)) -r)(t) (t) with a(t) is non-decreasing and approaches
Here, fuy (t; a()))
is the formulation of (t) with increasing and approaches to Eg as - oo. On the other hand, we would like to clarify that it is
á(t) substituted. Consequently, as â(f) + a, E(t) is non-
almost impossible empirically show the convergence of E(t), because {(t) is defined based on the probability that the estimation falls within a certain range (rather than a deterministic value) and hence difficult to compute in practice.
Summing up evidences (i) and (ii), then as + oo, we have E(t) + eg and limy A(T) cc. i.e., A(T) can be small and possibly as small as zero when T is sufficiently large.
Appendix K Additional Experiments
K.1
Incorporating Our Estimators into Baselines
In this section, we describe how to incorporate our estimators into RC, RUCB, and DT and obtain their versions RC-B, RUCB-B and DT-B. The modification ideas are similar: (i)
introduce a 3- 3-dimensional (3D) array V to record the choices of multiple evaluators; (ii) replace the
28

---

Cumulative Average Regret
2000
RC
DT DT-B(")
RC*-(())
Cumulative Weak Regret
1000
RCR
RC-B(())
DT-B(()
RUCB R(CB-B(")
RUCB
RUCB-B(")
1500
UCB
-BS-U(()
UCB
BS-UN(")
MBTW -BS-K(")
750
MBTW
BS-K(")
1000
500
500
250
0
2000
4000
6000
8000
10000
0
2000
4000
6000
8000
10000
Rounds
Rounds
(a)
(b)
Figure Algorithm convergence: (a) cumulative average regret, and (b) cumulative weak regret.
arm performance estimator in baselines with our estimators presented 2-5 of our Algorithm (iii) map the result back to the case without the definition of V such that the other steps in the oriinaal baselines remain applicable. The details of the bias-sensitive versions RC-B, RUCB-B, and DT-B are given as follows, where their main differences rely on which line to modify and what notations to use.
RC-B: Modify Algorithm in 10
Line 2: Initialize a 3D array < OKXKXx, Ms where M the number of evaluators;
Line 12: Replace it with lines 2-5 in our Algorithm 2 and set Uty(t) = + raji
Line 16: Replace it with Vk Vk 1ifc> d. and let Wii Σ ViJ.
RUCB-B: Modify Algorithm in
Line I: Initialize a 3D array V < OxxXXM, where M is the number of evaluators;
Line 4: Replace it with lines 2-5 in our Algorithm P and set Wi Pij + rigi
Line 14: Replace it with V V + 1f > d, and let Wij = Σtex ViJ.
DT-B: Modify Algorithm in
Line 1: Initialize 3D array V 0xxK*M where M is the number of evaluators;
Line 4: Replace it with lines 2-5 in our Algorithm 2 and set uty Pij + ray and 4y
Pij - Tifi
Line 17: Replace it with V V 1
1 6. and let Bij = ΣKEK ViJ.
K.2 Algorithm Convergence and Standard Error
Figure shows the convergence of average and weak regrets of our methods and other baselines. We have the following observations. First, our proposed BS-UN and BS-K K methods have much lower average and weak regrets than baselines (marked with dashed line). When t 10000, the reduction of average regret is more than 40%. Second, when compared with the baselines (marked with dashed lines), their bias-sensitive versions (marked with solid lines) achieve slower regret increase, verifying the capability of the bias estimation technique of our methods. This reduction is especially significant for DT and RUCB. Third, the performance of BS-UN and BS-K are similar, indicating the effectiveness of the bias estimation proposed in our methods.
Tables 6 and show the results of [ with standard error. Tables & Here, standard error defined as the standard deviation divided by the number of experiments (i.c., 100 in this work).
those of Table 2
29

---

Arm Heter. o²
Bias Concentr. Og
1.0
2.0
4.0
1.0
2.0
3.0
RC
1.79%
1338 1.39%
90..1.
2845.0..1%
1338 1.39%
11.38%
RUCB
1906..n.43%
2134
1.9440.700 10.70%
1154
2832 17%
2134
707%
1185 10.93%
DT
139611..1%
1425 2.59%
942
1.50%
2621 10.68%
1425 2.5%%
13.11.14%
MBTW
1220+1.92%
1,59 595%
1509
726.11.1%%
1769 10%
15009 11.09%
1448
UCB
1283 0.9%
1426 2.4%%
732
2581 +0.99%
1426 40%
706
RC-B (*)
1378.+1.5%%
161
1..1=11.3%
1050
2207 +:1.8%%
161 I 1.63%
803 8034:2.008
RUCB-B
993
1120 1120=0.47%%
709 4.9%
1191 15.91%
1055 1120_0.47%
DT-B
430 +3.99%
411 +44300%
342.%3.2%%
631 14.53%
411 4.430%
280 4.40 13%
BS-UN
690 63%
689 9..8%
387 15%
825 111.41%
689
98%
6377 +3.98%
BS-K (*)
654 4.2%%
1.13
4.7.1.3.2%
554 13.21%
7.3. 1..6%%
624 14.25%
Table 6: Cumulative average regret (L) Table with standard error.
Arm Heter. o²
Bias Concentr.
1.0
2.0
4.0
1.0
2.0
3.0
RC
596 22.42%
525 4.2.46%
502
1847
20.32%
525 42.46%
1.8.1
RUCB
101810.70%
114411.10%
719 1..3%%
1829
20.35%
1144
506.
DT
445 12.
492 1.5.5%
375 1..02%
1428 22.09%
492
492.5..5%%
191 191
MBTW
175+11.96%
140+ 122.12.82%
569
162 82%
92416.14%
UCB
553
43.3%%
336 336-3.39%
1583=11699%
54843.35%
153
RC-B (*)
649_1.48% 1.48%
869
727 40.97%
1119 1119
869 1.44%
502
RUCB-B
422 00.87%
48..0.05%
370 50.6%
604 12.35%
40.40%
406.40
DT-B
198 66.3%%
2..5%%
168 44.7%%
210
1 110
BS-UN
194.18.722
161 24.46%
44.01%
340+20.10 149.14%
16 124.46%
92 10.00%
BS-K
116 9.26%
90 14.02%
79 18.36%
60 16.39%
90 14.002%
82 11.70%
Table 7: Cumulative weak regret (4) in Table
with standard error.
K.3 Bias Estimation Error
Figure shows the convergence of the bias estimation error 1 (t) -m methods, including our proposed BS-UN and the bias-sensitive versions of baselines RC-B, RUCB-B, and DT-B. The following table shows the bias estimation error after 40000 rounds:
within 40000 rounds for our
(Num. of Arms, Num. of Evaluators)
(10,10)
(20,20)
(50,50)
RC-B (*)
0.03
0.02
0.06
RUCB-B (+)
0.03
0.04
0.04
DT-B (*)
0.10
0.08
0.16
BS-UN
0.04
0.04
0.03
Both the table and figure verify the convergence of the estimation error to small values for all our methods under diverse network scale.
K.4 Large-Scale Settings
To enable a more stable performance under large-scale settings, we make a minor modification on Algorithm{]) such that step 2 skipped after THR, on log iterations. where we set 50 due to its empirical performance. This is reasonable because step 2 is used for determining suitable initialization of Tmm 's. Once the T7.." have been approximately converged, no further initialization is needed. The result is presented in Table 10 First, our proposed BS- UN achieves lower average and weak regrets than baselines under large-scala settings. Second, DT-B also has lower regrets than the baselines. This indicates that by incorporating our bias estimation technique, DT-B is able to address biased evaluator. Finally, perhaps counter-intuitive under the large-scale settings, BS-UN outperforms BS-K. This is because the winning probability estimation at earlier iterations is relatively inaccurate, and BS-UN tends to explore more than BS-K and hence achieves better performance when the number of arms and evaluators are large.
30

---

0.4
-DT-6()
0.4
-0
Enar of Exgiuator Blas
-RD-817
Emrr of Exaluatrr Blos
-RC-81)
RC-811
-UCB-
RUCB-81
RUCBB(1)
0.3
US-UN())
05 0S-UN()
Eveluzter
0.3
BS-UNN))
0.
0.2
0.11
9.11
(a)
(b)
(c)
Figure 2:
Bias estimation error: (a) (10, 10), (b) (20, 20), and (c) (50, 50).
Number of Evaluators
Number of Arms
5
15
20
5
15
20
RC
1590 1.35%
1142
56.11.03%
2250
2568
10.06%
RUCB
2293
4..49%%
1924
2042
813 1.16%
2277 2277
1.0.1%
2499 10.9100
DT
1548 2.9
10731:3.0%%
1221
222122
695 1.97%
1854
2006
MBTW
1444 1.9%%
1.52+1.87%
1509 -1.5%
1218 1.90%
1260+
13300+1.77%
UCB
1604 22.8%%
1099+33.79%
12.22 3000%
63 +4.98%
1752
2115+00.32%
RC-B (*)
1801 1.22%
1370++1.82%
1694 1.75%
575 3.388%
2301 +0.32%
2707 +0.06%
RUCB-B (*)
90..9%
1102..004499
1115 0.37%
820 1..95%
1360
1868 18.84%
DT-B
360 15.22%%
375 1.551%
344 1..17%
169 1.838%
736
13.0%%
1156
BS-ON
688 6:1%%
722 1..0%%
621 +3, +3.2%%
626 2226+9.000
229 +1.7%
229
1157 11.16%
BS-K
588 4.29%
600 13.49%
638
1..55%
469 13.56%
88 12.79%
1021 1.2.8%
Table 8: Cumulative average regret (L) in Table 2 with standard error.
K.S
Additional Baselines
We have conducted experiments on Doubler (29), MultiSBM [29]. MaxInP (30]. and MaxMinLCB 3T.. Table provides the experimental results. As can be observed, our proposed BS-K and BS-UN approaches always outperform baselines in terms of both weak and average regrets.
K.6 Ablation Study: Description and Weak Regret
We first describe the estimators we considered in ablation study. For the arm performance estimator in Figure (a) and (c), we compare the following:
Weighted- Vottined-Vooinn--e UN: estimator in 22 while replacing the actual evaluator bias with the
estimated bias in (18);
Weighted-Voting-K: estimator in
Minimum-Deviatinnn UN: estimator in (66
Minimum-Deviation: K: estimator in 10
For the evaluator bias estimation in Figure 3 (b) and (d), we compare two groups of estimators: con-
ditional probability expression-based estimator (denoted by "COND"); optimization- based estimator (denoted by "OPT"", which is the bias estimator in (18). For the group of COND estimators, the bias estimated by
im Eig () > (,5) > 0.5)
(71)
(20 - 1) > 0.5)
which is derived based on the definition of in 3 For either of COND and OPT estimators, calculating the estimated 7mm and Pij are challenging, as calculation corresponds to solving
complex equation system (e.g., the equation system comprising (16) and (18) comprising (16) and (7h)). Thus, we compare three approaches to calculate their estimated values based on our designed estimators:
31

---

Number of Evaluators
Number of Arms
5
15
20
5
15
20
RC
689+2.455 15%
409 42.7700
497.2.96%
1303+1007%
1626+0.11%
RUCB
1272+0.877
979.1.10%
1067+1.200
181 181
135640.333
1.93+0.17%
DT
45.7%%
66.8%
4531%
1.2.+4..6%
+3.39%
802+3.82%
MBTW
177 113.
124 78%
12.392
16.1%%
307 +7766..30 63%
438 438
UCB
13..3.1
387 5.00%
491 44..4%%
77 1.1.07%
97 1..27%
1264 12.4.0
RC-B (*)
9.4 133%
785 785 1.50%
1005+1.7055
198 +3.7777%
1492+00.480 0.8%
1993+00. 12%
RUCB-B
392+0.
46840.6099
483 403.00.00
243 243_23.700 70%
707 40.77%
1 1146+0.58%
DT-B
177 +3.8%
165
410.7777
169 +9.5%
+17.311%
308 = 44.8%%
578 578++4.149
BS-UN
121 133. 16%
26.2%%
79 33.8%
108 52.06%
364 44.98%
543 1.3.1.999%
BS-K
57 19.0%%
73
13..4%%
75 111006
21 +. 19.88%
306 47.60%
420 55.40%
Table Cumulative weak regret (4) in Table with standard error.
Cum. Weak Regret ())
Cum. Average Regret (L)
(Num. Arms, Num. of Eval.)
(50,50)
(100,100)
(50,50)
(100,100)
RC
17494
18711 18.1110.00% 10.00%
18441 10.01%
19298 10.00%
RUCB
16625 -0.6%
17887 10.02%
1793
1.003%
18705 10.01%
DT
36341:30.1199
7656.18..1%%
6288 15.6%%
10993
19.96%
MBTW
2170 +:7...3..000
5725 +:2..44%
10293 6.66%
12013 5..4%%
UCB
15398 -0.2%%
16410 20.25% 25%
171964.0.133
17853 17853 +0.1129..
RC-B(*)
18074
187 1871640.000
1875440.0000
19313.20.0%%
RUCB-B(*)
15609 =1.2%
17871
=0. +0.00% 06%
17424
18694 18694=0.038 +0.03%
D
1481 111.92%
2850 19.70%
1907 10.557%
3703 18.56%
BS-UN(()
1628
5280-2.5777
93077
11533 +0 +0.33% .2%
BS-K(*)
3825 1.93%
17871
0.0%
10648 50.8%
18696
Table 10: Algorithm performance under large-scale settings.
Last Round Preference (denoted by "P"): Estimate evaluators' bias based on the estimated arm performance in the previous time slot, and then update the arm performance estimation
using (I6)
Mean Preference (denoted by "MP"): Estimate evaluators' bias based on EmEM Pij (t
1)/M, and then update the arm performance estimation using (I6)
Mean Preference with User Bias (denoted by "BMP"): The approach presented in Algorithm
To sum up, we compare seven approaches with different bias estimators and calculation methods: the case where the ground-trutt bias is known (denoted by "Known"). which serves the benchmark, COND-P, COND-MP, COND-BMP, OPT-P, OPT-MP, and OPT-BMP.
Now, we show the ablation study on average and weak regrets in Figure 3 performance estimator leads to a much lower average and weak regrets than that in Appendix A In addition, our proposed bias estimation approach achieves an average and weak regret that is closer to the case where the ground-truth bias is known, when compared with the other approaches.
Our proposed arm
K.7 Ablation Study: Times in Estimation Updates
shows the evaluation of different times of the estimation updates in lines 3-4 of Algorithm 2 Table 12
Note that to show a relatively obvious performance gap, we conducted experiments under a relatively large scale setting with 50 arms and 10 evaluators.
can be observed that "updating twice" leads the best performance. Further increasing the times of updates does not improve the performance. Intuitively, the main idea is to find better initial point for a more accurate estimation each time slot. According to Algorithm 2 in line each time slot, the arm performance estimation Pty (l 1) is initialized as the estimation ignoring the bias, and then the bias estimation in (L 1) is initialized based on the recent arm performance estimation. Note that up to now. it is obvious that both the bias and arm performance are far from ideal initial
32

---

Table 11: Experimental results under additional baselines.
Weak Regret ())
Average
Regret ())
Arm Heter.
o²
Bias Concentr.
ag
Arm
Heter. o²
Bias Concentr. ag
Doubler
791
815
889
1743
815
432
1612
1655
1693
2683
1655
885
MultiSBM
865
958
1045
1735
958
475
1710
1908
2055
2747
1908
1089
MaxInP
1394
1600
1617
2006
1600
711
2267
2539
2541
2982
2538
1289
MaxMinLCB
501
494
501
1613
494
220
1193
1227
1210
2628
1227
668
(*-
116
90
79
60
90
82
654
713
407
554
713
624
BS-UN(*)
194
161
94
340
161
92
690
689
387
825
689
637
Cumulative Average Regret
1000
Weighted-Voting--eee
Cumulative Average Regret
Known
COND-P
-OPT-P
Belgghedd-Voling-*
800
Minimum-Deviatoon-ue Deviation-UN())
400
COND-BMP -OPT-BMP())
COND-MP
-OPT-MP
Minimum- SeammmDDviille DeviationK("")
600
400
200
200
500
1000
1500
2000
500
1000
1500
2000
Rounds
Rounds
(b)
Weighted-Voting-UUN
Cumulative Weak Regret
400
Known
Cumulative Weak Regret
Weighted-Votingg
COND-P
-OPT-P
800
Minimum- Mirimum-Deviation-Pee Deviation-K(")
Deviation-UN()
300
COND-MP
COND-BMP
-OPT-MP
OOPT-BMP()
600
200
400
100
200
0
0
0
500
1000
1500
2000
0
500
1000
1500
2000
Rounds
Rounds
(c)
(d)
Figure 3: Ablation study: average regret of estimators on (a) arm performance and (b) bias; weak
regret of estimators (c) arm performance and (d) bias.
point for estimation update, because they are determined by ignoring the bias. To address, in line we update Piy (t - 1) and 9)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 and corresponds to the actual updates of the estimation.
K.8 Regret Increase under Biased Evaluators
Table 13 shows the algorithm performance without and with evaluators' bias, motivating this work on addressing biased evaluators. We have the following observations. (i) With the presence of evaluators' bias, algorithms experience obvious increase of average and weak regrets, leading to the necessity of proposing methods address the evaluators' bias. (ii) When there are no evaluators' bias, our proposed methods do not induce huge performance degradation, i.e., the average and weak regrets of our proposed methods remain relatively low. (iii) When evaluators' bias exist, our proposed methods achieve lower average and weak regret than most of the basclines.
33

---

Table 12: Ablation Study: Different Number of Estimation Updates.
Cum. Weak Regret (L)
Cum. Average Regret (4)
Rate of Best Arm (?)
Without Line 2
3752
6311
0.79
Update once
2060
5416
1.00
Update twice
1904
5339
1.00
Update 3 times
2021
5371
1.00
Update 4 times
1983
5369
1.00
Cumulative Weak Regret (L)
Cumulative Average Regret ())
No Bias
Beta(2, 1)
Increase
No Bias
Beta(2, 1)
Increase
RC
122 1.221.397
52542.46%
x4.31)
132++.13%%
1338+1.39%
x5.78)
RUCB
154 83.
1144+11.00%
(x7.43)
50240.34%
2134 70%
(3.667)
DT
4..4.60%
49245.45%
(x15.19)
148 148 +..0%%
1425+2.59%
(x9.61)
MBTW
1 11415.4754
162 82%
(x14.15)
1524
1539
(x1.01)
UCB
13
548+3335%
(x42.26)
401 +0.9%%
1426+-2.4677
(x3.56)
RC-B(*)
171 +1.32%
869 1: 1.45%
(x5.09)
264
161 1611 1.63%
(x6.10)
RUCB-B(*)
361 +0.61%
480+0.658
x1.33)
887 80.30%
1120 40.7%
[x1.26)
DT-B(*)
36418.02%
210 .5%
(5.78)
126
411 + 30%%
(x3.27)
BS-UN(*)
31 42.6%
161 244.4%% 40%
x5.24)
447 20.77%
689
+5 98%
x1.44)
BS-K(*)
41 +2.44%
90 90 14.02%
x2.22)
458 40.4%%
4.3.4.60%%
(x.56))
Table 13: Regret increase under the presence of evaluators' bias. The methods marked with "(*)" are our methods. The best, second, and third best results are marked in bold text, underline, and dashed underline, respectively. All these experiments are conducted under unknown bias case, expect for those of BS-K.
Appendix L Society Impact
This work has positive society impact improving the dueling bandits algorithm performance in the presence of biased evaluators. For negative society impact, may enable the agent (e.g.. a platform) to detect the bias of evaluators, leading to certain privacy leakage. To address this, the proposed algorithm may be packed into package and restrict the access of the agent to the bias estimation result.
34


Reviews:
[{"review_id": "8hVD8wuAR7", "reviewer": "Reviewer_wbVs", "summary": "The authors tackle the problem that the binary feedback in a dueling bandit scenario, e.g. given by a human evaluator, might be biased. In their setting, the bias refers to the probability that the expected feedback from a specific evaluator coincides with the ground truth pairwise winning probabilities. In the paper, two settings, with known and unknown bias, are covered. For both, they provide a closed form to estimate the pairwise winning probabilities between the arms (and resp. the bias of the evaluators) and propose UCB-based algorithm to solve the regret minimization problem, while they focus on average and weak regret. In a theoretical analysis, the authors provide regret bounds for both cases, which is in the case of unknown bias far from trivial due to the non-convexity of the problem. In an experimental study, it is shown that their methods suffer less regret in comparison to classical dueling bandit algorithms as baselines and moreover, that these baselines could be extended and improved by their approach for the bias estimation.", "questions": "Questions:\n- I am wondering how the weak and average regret can have the same regret bounds. As the name suggests, the weak regret is usually lower than the average regret (assuming that not two times the same arm is chosen during a time step), so intuitively I would expect a tighter regret bound for the weak regret. Can you discuss how tight the bounds are? What is about the strong regret?\n\n- Usually, in dueling bandit methods like in Relative UCB, only the first arm is chosen as the one that maximizes the upper confidence bound, and the second arm is chosen as the one that is the \"best competitor\" for the first chosen arm where the winning probability of the first arm is minimized. Formally, the first chosen arm would be $x_1(t) = max_i UCB_i(t)$ and the second chosen one $x_2(t) = min_j UCB_{i,j}(t)$. Have you tried out this approach or do you have a reason why you don't do it like this?\n\n- How does your method with unknown bias behave if no bias is present? Does it correctly recognize that there is no bias? Can it keep up with the baselines like RUCB or double thompson sampling? Does the difference between your methods and the baselines become bigger with larger bias? For this, some experiments with different beta distributions to sample the bias would be nice", "limitations": "The authors mentioned some limitations, like the assumption that the bias is fixed over the whole time horizon and the lack of experiments on real-world human data. Other potential limitations (maybe a slower convergence of the estimated pairwise probabilities if no bias is present?) are not made clear and cannot be derived by the reader from the shown experiments.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The topic is motivated well with a recently relevant application of the output selection of LLMs. Although I did not read the proofs in the appendix in full detail, the biggest strength of the paper is that the proposed approach is theoretically grounded and provided with a regret analysis for weak as well as for average regret that generalizes over the known regret bounds for the case of no existing bias. The whole paper is well written and easily understandable. However, a weakness is the experimental study, which covers to the best of my understanding only synthetic data and only one instantiation of the distribution from which the biases are sampled. Here, a more detailed sensitivity analysis of how the methods behave, for example, for no bias at all or for different beta distributions from which the biases are sampled, would be insightful.", "was_revised": true, "final_justification": "As already stated above, the paper is solid work regarding the well-motivated idea, the proven regret bounds, and the experimental study. I want to positively outline the rebuttal of the authors who were willing to make some points clearer in the final version of their paper and, in addition, provided some new, insightful experimental results.", "rebuttal": "Thank you for your suggestions and identifying the strength of this work on \"theoretically grounded\", being \"motivated well\", and \"well-written\". \n\n**Bias Distribution:** \nThank 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:\n- 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%. \n- 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.\n\n**Relative UCB:**\nWe have conducted experiments on Relative UCB, which is denoted by \"RUCB\" in the manuscript. \n\n**Weak and Average Regrets:**\nThank 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. \n\n**Synthetic Data:**\nThis 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."}, {"review_id": "AVGa8N6qNW", "reviewer": "Reviewer_dKuD", "summary": "The authors consider the duelling bandit problem with finite arms and biased evaluators.\nIn particular, they assume that there is a finite set of evaluators that are either provide feedback according to the true preferences or the contrary in pairwise comparisons. Each evaluator provides good feedback with certain probability (their bias variable).\nIn the first part, the authors derive a no-regret algorithm for the case when the evaluators' biases are known.\nIn the second part, they extend the case where both the preferences and the biases are unknown.\nFinally, the authors provide experimental evidence that their proposed algorithms outperform algorithms that disregard evaluator biases and their confidence estimation can be incorporated in many other algorithms to improve their performance.", "questions": "1. Why do the authors choose the Borda Score as their notion of optimality in the general preference setting? I would encourage them to discuss strengths and weaknesses of this design choice. E.g. how does it represent minorities in the annotator pool?\n2. In Line 222-223, the authors claim \"This sublinearity result is consistent with and generalizes those existing works on dueling bandits\nwithout considering evaluators’ bias (e.g., [13])\" could they provide an elaboration on this claim?\n3. The authors use the term \"highly coupled\" multiple times. Could they specify what they mean exactly? I found this fairly ambiguous.\n4. Line 264-265, the authors claim \"We empirically show that performing such updates twice leads to the best performance\" but I could not find these empirical evaluations. Could you point me to them?\n5. Could the authors also report the cumulative regret curves in the Experiments section corresponding to Table 1 and 2 instead of just reporting the values at a specific time-step?\n6. Could the authors elaborate why they choose RC, RUCB, DT, and MBTW as comparison algorithms and omit other works such as Double, MultiSBM [Ailon et al. 2014], MaxInP [Saha, 2021] and MaxMinLCB [Pasztor et al. 2024] that show good performance on the standard duelling bandit problem?", "limitations": "Please see the Weaknesses section. I have listed my concerns there.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I found the following points to be strengths of this paper:\n1. General preference case not restricted to the Bradley-Terry or Logistic case. This means it is applicable to complex preferences that might not be transitive or follow a reward model.\n2. The results on estimating the pairwise comparison probabilities and biases are general and can be incorporated in many other algorithms\n3. The investigation of biases (especially in human feedback) is more and more crucial given their use in training frontier models and deployed to the general public\n\nWeaknesses:\n1. Considering finite arms and set of evaluators limit the applicability of these results to applications such as training LLMs which the authors use as a motivating example\n2.  I found the motivating example of a company choosing LLMs for deployment to be a bit misleading. In natural language, biases are often contextual (e.g. depends on the question posed). Accordingly some models might be better for certain contexts than others and hard to find a single best option. Additionally, these contexts are infinite (but structured) and the proposed approach can not be easily extended to this case.\n3. In the general preference model setting, the definition of optimality is non-trivial. The authors choose the Borda winner as their notion of optimality but do not discuss its advantages and disadvantages such as neglecting minorities.\n4. While the experiments provide some experimental evidence its is limited to 10 arms and 10 evaluators and a single preference model. Further experiments in larger settings are required to demonstrate the applicability of their results.", "was_revised": true, "final_justification": "To my judgement, this paper has significant contribution and the authors' adequately answered all the questions I raised in my review. I maintain my positive score and support this work's acceptance.", "rebuttal": "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.\n\n**Finite Arms and Evaluators:**\nWe 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.  \n\n**Bias Due to Contextual Information:**\nThank 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. \n\nI. 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. \n\n**Advantage and Disadvantage of Optimality Definition:**\nIn 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. \n\nWe 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.  \n\n**Experiments with More Arms/Evaluators and Preference Model:** \nDue 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.\n\n**Sublinearity Result Being Consistent with Existing Works:**\nWith 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.\n\n\n**Explanation on Highly Coupled:**\nThe \"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.\n\n**Explanation and Evaluation on \"Update Twice\":**\nThe 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.\n|Algorithms|Cumulative Weak Regret|Cumulative Average Regret|Rate of Best Arm|\n|-------|-------|-------|-------|\n|Without Init. in Line 2|3752|6311|0.79|\n|Update once|2060|5416|**1.00**| \n|Update twice|**1904**|**5339**|**1.00**|\n|Update 3 times|2021|5371|**1.00**|\n|Update 4 times|1983|5369|**1.00**| \n\nIt 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. \n\n\n**Cumulative Regret Curve:**\nThe cumulative regret curves are provided in the Appendix due to the space limit. Please see Figure 1 in Appendix J.2 for details.\n\n**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. \n|Weak Regret|$\\sigma^2=1.0$|$\\sigma^2=2.0$|$\\sigma^2=4.0$|$\\alpha_{\\text{B}}=1.0$|$\\alpha_{\\text{B}}=2.0$|$\\alpha_{\\text{B}}=3.0$|\n|-------|-------|-------|-------|-------|-------|-------|\n|Doubler|791|815|889|1743|815|432|\n|MultiSBM|865|958|1045|1735|958|475| \n|MaxInP|1394|1600|1617|2006|1600|711| \n|MaxMinLCB|501|494|501|1613|494|220| \n|BS-K(*)|**116**|**90**|**79**|**60**|**90**|**82**| \n|BS-UN(*)|194|161|94|340|161|92| \n\n|Average Regret|$\\sigma^2=1.0$|$\\sigma^2=2.0$|$\\sigma^2=4.0$|$\\alpha_{\\text{B}}=1.0$|$\\alpha_{\\text{B}}=2.0$|$\\alpha_{\\text{B}}=3.0$|\n|-------|-------|-------|-------|-------|-------|-------|\n|Doubler|1612|1655|1693|2683|1655|885| \n|MultiSBM|1710|1908|2055|2747|1908|1089| \n|MaxInP|2267|2539|2541|2982|2538|1289| \n|MaxMinLCB|1193|1227|1210|2628|1227|668|\n|BS-K(*)|**654**|713|407|**554**|713|**624**| \n|BS-UN(*)|690|**689**|**387**|825|**689**|637| \n\nThe 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."}, {"review_id": "GhlD9WHchV", "reviewer": "Reviewer_TcVQ", "summary": "This paper addresses the previously underexplored problem of biased evaluators in the dueling bandits setting, where comparisons between arms may be corrupted. The authors first consider a benchmark setting where evaluator biases are known, and propose a bias-sensitive UCB algorithm with a novel unbiased estimator. They then extend this to the more realistic setting where the bias is unknown, proposing an iterative estimator. The paper provides theoretical regret bounds in both cases, and demonstrates that the latter has the same order of bound on the regret as the former. Extensive experiments demonstrate that the proposed methods significantly outperform standard dueling bandit algorithms, especially when evaluator bias is heterogeneous. The proposed techniques are general and can be incorporated into existing dueling bandit frameworks.", "questions": "As noted earlier, my primary concern and the reason for the current score is related to the regret bounds. I would appreciate clarification on the following points:\n1. Based on your analysis and the observed behavior of cumulative regret over time in the experiments, do you believe that the linear dependence on $T$ in the regret upper bounds of Theorems 1 and 2 is fundamentally unavoidable when multiple evaluators are involved? If so, could you provide some theoretical or empirical evidence to support this? Conversely, if this dependence might be removable, what do you see as the main technical obstacle? Do you have any ideas or directions for how this dependence could potentially be mitigated?\n2. What is the justification for assuming the existence of a ground-truth preference matrix $p_{ij}$? For instance, in the context of LLM selection—where feedback is inherently subjective—what would this ground truth represent?\n3. Could you elaborate further—beyond the brief explanation in lines 71–72—on how you address the challenges involved in deriving the regret bounds?\n4. You mention that your proposed estimators can be readily incorporated into existing algorithms to improve their robustness under biased evaluation. How challenging do you anticipate it would be to derive regret bounds for these modified algorithms? Can the techniques used to prove Theorems 1 and 2 be adapted to this setting, or would each algorithm require a distinct and potentially more complex analysis?\n5. In Lemma 3, you derive the true confidence radius for the unknown bias setting, which involves the parameter $\\eta_m$ and thus cannot be computed exactly by Algorithm 2. However, why not substitute $\\eta_m$ with its estimate $\\hat{\\eta}_m$ in this expression, rather than relying on the less precise approximation $\\hat{r}$ used in Algorithm 2? Could this substitution lead to improved empirical performance or tighter regret bounds?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n- **Quality:** The paper’s main claims are supported by rigorous and well-structured proofs, demonstrating a solid theoretical foundation. Additionally, the paper includes a thorough experimental evaluation that demonstrates the superiority of the proposed methods over existing baselines and provides insight into the behavior of the key parameters introduced throughout the study.\n- **Clarity:** The authors clearly motivate the study of biased evaluators through a compelling example involving LLM selection. The proposed algorithms and accompanying proof techniques are presented with intuitive explanations in the main text, and their effectiveness is validated through a comprehensive and rigorous experimental evaluation.\n- **Significance:** This work advances the state of the art by introducing techniques that enable effective learning in environments with biased feedback. Beyond proposing novel algorithms, the authors demonstrate that their methods can be integrated with existing approaches, which enhances the significance of this work. \n- **Originality:** This is the first work to address the dueling bandits problem under biased feedback. Although the authors build on established convex optimization techniques, they employ them in a novel manner to construct provably unbiased estimators with theoretical regret guarantees.\n\n**Weaknesses:**\nRather than separating into broad quality, clarity, significance and originality categories, I will outline my main concerns in a more detailed manner below.\n\n- The primary concern with this work lies in the significance of the regret bounds presented in Theorems 1 and 2. As noted in Corollary 1, when the bias can take on multiple values (i.e., $|\\mathcal{B}|>1$), the cumulative regret becomes linear in $T$ which is no better than the regret of a naive algorithm that selects two arms at random in each round. This issue is further exacerbated in Theorem 2, where an additional error term of the form $O(\\sum^{T} \\xi(t))$ appears. Unfortunately, the authors do not provide a theoretical bound for this term; instead, they offer only empirical evidence suggesting that it converges to a small value $T\\epsilon$, which remains linear in $T$. As a result, this limitation substantially weakens the theoretical contribution of the paper.\n- This concern is further amplified by the absence of a lower bound that would justify the observed linear cumulative regret in the presence of multiple biased evaluators. Moreover, the experimental results do not clearly indicate whether the cumulative regret grows sublinearly with the number of rounds. This raises the question of whether the linear regret is fundamentally unavoidable in this setting, or if a more refined analysis would yield improved bounds. Without addressing this, the theoretical contribution remains incomplete.\n- The authors motivate the biased evaluators setting with an example involving a company acting as the agent, multiple LLMs as arms, and users as evaluators. However, the framework assumes the existence of a ground-truth pairwise preference matrix $p_{ij}$, which is not clearly justified in this context. Given that preferences over LLM outputs are inherently subjective and user-dependent, it is unclear why such a universal ground-truth should exist. This raises questions about the practical usability of this model.\n- In lines 143–152, the authors state that their analysis covers both average and weak regret. However, since weak regret is always upper bounded by average regret, it seems the provided bounds effectively only analyze the latter. As a result, the regret bound, while technically applying to both, may be loose for the weak regret. Notably, in the non-biased dueling bandits setting, it is known that cumulative weak regret can be independent of $T$ [1], whereas the bound presented here remains $O(\\sqrt{T})$, even under similar conditions. This observation is further supported by the experimental results, which show that weak regret is significantly lower than average regret.\n- Returning to the regret upper bound in Theorem 2, the inclusion of the parameter $\\xi(t)$ renders the bound somewhat incomplete, as $\\xi(t)$ lacks a closed-form expression or meaningful interpretation in simple terms. Moreover, the authors do not provide a theoretical guarantee that the resulting term $O(\\sum^{T} \\xi(t))$ is bounded, relying instead on empirical evidence presented in Appendix I. \n\nOther concerns – \n- For a given evaluator $m$, the bias parameter $\\eta_{m}$ in Equation (3) is assumed to be uniform across all arm pairs.\n- In Appendix J.1, the authors describe how their techniques can be integrated into existing dueling bandit algorithms to handle biased evaluators and verify the effectiveness of this approach through experiments. However, they do not provide any accompanying theoretical analysis to support these extensions.\n- The regret upper bounds in Theorems 1 and 2 are lengthy, involve numerous parameters, and are difficult to interpret. It would be preferable to move the full expressions to the appendix and present a simplified or more interpretable version in the main text.\n- Additional proofreading would improve the paper. For example, “pairs” should be used instead of “pair” in line 234. The notations $p_{ij}(t)$ and $\\eta_m(t)$, as used in line 240 and elsewhere, should be without $t$. In line 253, “update” should replace “updates.” In line 264, the word “for” should be removed. The definition of HF in line 281 is unclear. Line 287 appears to refer to “Assumption 3,” but likely means “Definition 3.” Finally, the parameter $t_0$ in Equation (21) seems to be used without being defined in the main paper.\n\n[1] Saad, El Mehdi, et al. \"On weak regret analysis for dueling bandits.\" Advances in Neural Information Processing Systems 37 (2024): 40752-40791.", "was_revised": true, "final_justification": "This is the same as my comment to the authors below: \n\none of my principal concerns was the linear dependence on $T$ in the regret upper bounds of Theorems 1 and 2. I was pleased to see that the authors have managed to eliminate this term from Theorem 1. Regarding my other concerns—the apparent linear $T$ dependence through $\\xi(t)$ in Theorem 2 and the lack of proof schemes for alternative baselines—I accept the authors’ statement that these are challenging issues that can be addressed in future work. I also acknowledge the rationale for the existence of an inherent performance matrix in this setting.", "rebuttal": "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\".\n\n**Regret Bound Analysis:**\nWe 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).\n-  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. \n- 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:\n$$\n\\text{Event~} X_{ij}(N_{ij},t) :  \\text{There exists } b \\in \\mathcal{B} \\text{ such that } n_{ij}^{b} - \\frac{N_{ij}}{B} < - \\sqrt{ \\frac{N_{ij}\\log(B t^{2 \\alpha})}{2} } \\text{ and } \\sum_{b \\in \\mathcal{B}} n_{ij}^{b} = N_{ij}.\n$$\nIntuitively,  this is the event where the exploration is highly skewed among evaluators, as the previous example suggests. \nThen,  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. \n\nBased 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.\n\nFor 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.  \n\nTo 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:\n- We identify the **novel problem** of biased evaluators in dueling bandits.\n- 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.\n- 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. \n- 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. \n\n\n**Weak Regret and Average Regret:**\nWe 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.  \n\n\n**The Inclusion of $\\xi(t)$ for Unknown Bias Case:** \nWe 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. \n\n\n**Existence of a Ground-Truth Pairwise Preference Matrix:**\nWe 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. \n\n**Uniform Bias:**\nThank 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.\n\n\n**Elaboration on Addressing the Challenge of Bound Analysis:**\nThe 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. \n\n\n**Analysis on the Incorporation of Bias Estimation to Baselines:**\nSince 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. \n\n\n**Confidence Radius in Lemma 3:**\nIf 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$.\n\n**Typos and Formatting:**\nWe will address them in the manuscript."}]

Author rebuttal:

Meta-review: The authors address the issue of bias in binary feedback in a dueling bandit scenario. In their model, bias is defined as the probability that the expected feedback from a specific evaluator will coincide with the true pairwise winning probabilities. The paper covers two settings, with known and unknown bias. They provide a closed-form expression for estimating the pairwise winning probabilities between arms for both. They also propose a UCB-based algorithm for solving the problem of minimising regret, focusing on average and weak regret. In their theoretical analysis, the authors provide regret bounds for both cases. An experimental study shows that their methods incur less regret than classical dueling bandit algorithms.

Overall, the reviewers are quite positive about the paper. In their reports, they raised a couple of comments and concerns, however, these could essentially be resolved in the rebuttal and subsequent discussion.
Decision: Accept (spotlight)