Active preference learning for ordering items in- and out-of-sample
Authors: Herman Bergström
Emil Carlsson
Devdatt Dubhashi
Fredrik D. Johansson
Venue: NeurIPS 2024 poster (2024)
Keywords: ordering
active learning
preference learning
medical imaging
human feedback
pairwise comparison
Primary area: active_learning
TL;DR: Active preference learning supports fast ordering of items in- and out-of-sample. Sample complexity analysis justifies active sampling criteria.

Abstract: Learning an ordering of items based on pairwise comparisons is useful when items are difficult to rate consistently on an absolute scale, for example, when annotators have to make subjective assessments. When exhaustive comparison is infeasible, actively sampling item pairs can reduce the number of annotations necessary for learning an accurate ordering. However, many algorithms ignore shared structure between items, limiting their sample efficiency and precluding generalization to new items. It is also common to disregard how noise in comparisons varies between item pairs, despite it being informative of item similarity. In this work, we study active preference learning for ordering items with contextual attributes, both in- and out-of-sample. We give an upper bound on the expected ordering error of a logistic preference model as a function of which items have been compared. Next, we propose an active learning strategy that samples items to minimize this bound by accounting for aleatoric and epistemic uncertainty in comparisons. We evaluate the resulting algorithm, and a variant aimed at reducing model misspecification, in multiple realistic ordering tasks with comparisons made by human annotators. Our results demonstrate superior sample efficiency and generalization compared to non-contextual ranking approaches and active preference learning baselines.

Active preference learning for ordering items in- and out-of-sample
Herman Bergström'
Emil Carlsson" *
Chalmers University of Technology and University of Gothenburg
Sleep Cycle AB
Chalmers University of Technology and University of Gothenburg
hermanb@chalmers.co
Devdatt Dubhashi
Fredrik D. Johansson
Chalmers University Technology and University of Gothenburg
Chalmers University of Technology and University of Gothenburg
Abstract
Learning ordering of items based on pairwise comparisons is useful when items are difficult to rate consistently on an absolute scale, for example, when annotators have to make subjective assessments. When exhaustive comparison infeasible, actively sampling item pairs can reduce the number of annotations necessary for learning an accurate ordering. However, many algorithms ignore shared structure between items, limiting their sample efficiency and precluding generalization to new items. It is also common disregard how noise comparisons varies be- tween item pairs, despite it being informative of item similarityy In this work, we study active preference learning for ordering items with contextual attributes, both in- and out-of-sample We give an upper bound on the expected ordering error of a logistic preference model as function of which items have been compared. Next, we propose an active learning strategy that samples items to minimize this bound by accounting for aleatoric and epistemic uncertainty in comparisons. We evaluate the resulting algorithm, and a variant aimed at reducing model misspecification. in multiple realistic ordering tasks with comparisons made by human annotators. Our results demonstrate superior sample efficiency and generalization compared to non-contextual ranking approaches and active preference learning baselines.
Introduction
The success of supervised learning is built on annotating items at great volumes with small error. For subjective assessments, however, assigning value from arbitrary rating scale be difficult and prone to inconsistencies, causing many to favor preference feedback from pairwise comparisons (Yannakakis and Martínez, 2015; Christiano et al., 2017: Ouyang al., 2022; Zhu et al., 2023). Preference feedback is sufficient to learn an ordering of items (Fürkrranz and Hüllermeier, 2003), but for n items, there are O(n²) possible pairs of items to compare. A common solution to crowd-sourcing (Chen et al., 2013; Yang et al., 2021; Larkin et al., 2022), but many tasks require domain expertise, making annotations expensive collect. This is the case in the field of medical imaging. where annotations require trained radiologists (Phelps et al.. 2015; Jang et al., 2022; Lidén al., 2024; Tärnåsen and Bergström, 2023). So, how can we learn the best ordering possible from a limited number of comparisons?
"qqual contribution. Work was mainly performed while the author was a PhD student at Chalmers Univer- sity of Technology.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Classically, this problem is solved by active learning, sampling comparisons based on preference feedback and estimated item scores (Herbrich et al., 2006; Maystre and Grossglauser, 2017: Heckel et al., 2018), 8). However, consider radiologist who wants to quantify the expression of disease in a collection of X-ray images. Purely preference-baser algorithms utilize only the outcomes of comparisons but ignore the contents of the X-rays, which can reveal similarities between items and inform an ordering strategy. Moreover, the set we want to order is often larger than the set of items observed during training-we may want to rank new X-rays in relation to previous ones. This cannot be solved by learning per-item scores alone. As an alternative, active learning for classification can be used to fit map from pairs of item contexts 24, 2 (e.g., the contents of images) to the comparison >> J. that can be applied to old and new items alike (Houlsby et al., 2011; Qian et al., 2015). However, as we show in Section 4, learning this map to recover complete ordering is distinct from the tasks preference learning is commonly used for, and existing algorithms lack theoretical justification for this application. Moreover, formal results for related problems, such as contextual bandits or reinforcement learning (Das et al., 2024; Filippi et al., 2010; Zhu et al., 2023; Bengs al., 2022), do not translate directly to effective active sampling criteria for ordering. There is a small body of work on learning a contextual model to recover the complete ordering (Jamieson and Nowak, 2011; Ailon, 2011) but these either assume noiseless preference feedback or that the noise is unrelated to the similarity of items, which is unrealistic for subjective assessments.
Contributions. We propose using a contextual logistic preference model support efficient in- sample ordering and generalization to new items. Our analysis yields the first bound on the expected ordering error achievable given a collected set of comparisons (Section 4). This result justifies an active sampling principle that accounts for both epistemic and aleatoric uncertainty which we im- plement in greedy deterministic algorithm called GURO (Section 5). We further propose hybrid variant of the contextual preference model, compatible with GURO as well as existing sampling strategies, that overcomes model misspecification by adding per-item parameters (Section 5.1). We evaluate GURO and baseline algorithms in four diverse ordering tasks, three of which utilize com- parisons performed by human annotators (Section 6). Our sampling strategy compares favorably to active preference learning baselines, and our hybrid model benefits both GURO and other sampling criteria, achieving the low variance of contextual models and the low bias of fitting per-item param- eters. This results in faster convergence in-sample, better generalization to new items, and efficient continual learning when new items are added.
Ordering items with active preference learning
Our goal is to learn an ordering of items I according to unobserved score y/ E R. defined for each item E I. The ground-truth ordering of I is determined by a comparison function Tay := [y, > Vyl. where Tij indicates that ranks higher than j. We assume there are ties.
We define the ordering error Rz (h) of a learned comparison function h I I + {0,1} as the frequency of pairwise inversions under a uniform distribution of item pairs,
2
Rz(h) nnn 1)
[[h(i.)) + myl iæjEI
Σ
(1)
where n = [Z]. This error is equivalent to the normalized Kendall's Tau distance (Kendall, 1948).
Hypotheses h are learned from preference feedback-noisy pairwise comparisons Cit E 10 } for items (i,5) related to their score, for example, provided by human annotators. Cj = 1 indicates that an annotator perceived that item has a higher score than j. i.e., that they prefer over j. Our goal to minimize the ordering error (h) for a fixed budget T 2 of adaptively chosen comparisons.
We are interested in contextual problems, where each item i E I is endowed with item-specific attributes x, X C Rdd As we will see, this permits more sample-efficient ordering and learning algorithms that can order items out-of-sample, trained on comparisons of a subset of items ID S I and generalizing to I \ Ip. Ordering algorithms based only on preference feedback cannot solve this problem since observed comparisons are uninformative of new items.
Our active preference learning scenario proceeds as follows: 1) A learner is given an annotation budget T, a pool of items In C and item attributes 2; for E In. 2) Over rounds / = 1,..., T, the learner requests comparison of two items ic, ID according to sampling criterion and
2

---

receives noisy binary preference feedback e p(Ciy), independently of previous comparisons.
3) After T rounds. the learner returns a comparison function : I x I + {0, 13. We denote the history of accumulated observations until and including time / by D. = (i, (ft, Jr, (t))
We assume that comparisons Cay follow logistic model applied to the difference between item scores, p(Cij 1) = (3 Wi), the so-called Bradley-Terry model (Bradley and Terry, 1952), which assumes linear stochastic transitivity (Oliveira al., 2018). Throughout, a(2) = 11 + e=*) and (z)) its derivative at z. Specifically, we study the case where yi is a linear function of item attributes, y/ = 0__ x; with 6. E Rd the ground-truth coefficients. Thus, comparisons are determined by logistic regression model applied to the attribute difference vector Zij == I2 T.j+
P(C, = 1) = (0 zz))
(2)
We face two kinds of uncertainty when actively learning the model in (2): epistemic and aleatoric. Epistemic uncertainty, or model uncertainty, is the uncertainty about the true parameter O., while aleatoric uncertainty is the irreducible uncertainty about labels due to noisy annotation.
3 Related work
Active Preference Learning: Preference learning (Fürnkranz and Hüllermeier, 2003; Chu and Ghahramani, 2005) is related to the problem of learning to rank (Burges et al., 2005; Busse et al., 2012). When using adaptively chosen comparisons may be posed as an active learning or bandit problem (Brinker, 2004; Long et al., 2010; Silva et al., 2014; Ling et al., 2020). Non-contextual ac- tive learners, such as TrulSkill (Herbrich et al., 2006; Minka et al., 2018), Hamming-LLUB (Heckel et al., 2018), and Probe-Rant Rank (Lou et al., 2022) produce in-sample preference orderings, but must be updated if new items are to be ranked. Contextual algorithms, such as BALD (Houlsby et al., 2011), mitigate this by exploiting item structure and Kirsch and Gal (2022) show that many recently proposed contextual active learning strategies may be unified in a framework based on Fisher infor- mation. Similarly, methods have been proposed to recover linear preference model by adaptively sampling paired comparisons (Qian et al., 2015; Massimino and Davenport, 2021; Canal et al., 2019). Still, this setting differs from ours in that we emphasize recovering the full ordering, not perfectly estimating the parameters. While it is true that knowing the parameters is sufficient to order the list, reducing uncertainty for all parameters equally will likely be wasteful (see Section 4). Ailon (2011) I) offer guarantees for ordering using contextual features in the noiseless setting, while Jamieson and Nowak (2011) analyze the setting where noise is unrelated to item similarity.
Bandits: Bandit algorithms with relative or dueling feedback (Yue and Joachims, 2009; Bengs et al., 2021; Yan al., 2022) also learn from pairwise comparisons, and have been proposed both in contextual (Dudík et al.. 2015) and non-contextual settings (Yue et al., 2012) to minimize regret or identify top-k items. Bengs et al. (2022) proposed CoLSTIM, contextual dueling bandit for regret minimization under linear stochastic transitivity, matching (2), and Di et al. (2023) gave variance- aware regret bounds for this setting. However, algorithms that find the top-k items, such as pure exploration bandits (Fang, 2022; Jun et al., 2021), can be arbitrarily bad at learning full ordering (see Appendix D). Related are also George and Dimitrakakis (2023) who learn Kemeny rankings in non-contextual dueling bandits, and Wu et al. (2023b) who minimize Borda regret. Zhu et al. (2023) studies the problem of estimating a preference model from offline data. Our analysis uses techniques from logistic bandits (Filippi et al., 2010; Li et al., 2017; Faury et al., 2020; Kveton et al., 2020).
RLHF: Preference learning is commonly used when training large language models through rein- forcement learning with human feedback (RL.F)) (Christiano et al., 2017; Bai et al., 2022; Ouyang et al., 2022; Wu et al., 2023a). In this line of work, Zhu et al. (2023) provide guarantees on the sam- ple complexity of learning preference model from offline data. They leverage similar tools from statistical learning and bandits as we do. In contrast to their work, we provide sampling strategies for the online setting. Mehta et al. (2023) consider active learning for RLHF in a dueling bandit framework where the goal is to optimize a contextual version of the Borda regret. Concurrent work by Mukherjee et al. (2024) and Das et al. (2024) studies similar problem, as we do here, in the RLHF setting but with the objective to identify an optimal policy in a contextual bandit with dueling feedback. In contrast to their objective, we are interested in recovering the ordering of items. Das et al. (2024) use similar bandit techniques as we do, and their selection criterion, when adapted for ordering, corresponds to our NormMin baseline (see Section 6).
3

---

4 Which comparisons result in a good ordering?
We give an upper bound on the ordering error (h) for hypothesis fit using the feedback from a given set of 'I' comparison queries 2r = ((11.)1,,.... (&c, jr)). In other words, the bound attempts to answer the question "if we make queries 2r, how good can we expect our resulting model to be at ordering the items in I?". That is, we condition on the queries themselves and reason about the uncertainty due the stochastic feedback ct. In Section 5, we use insights from the result to design an active learning algorithm.
We restrict our analysis the logistic model in (2) and denote by R(0) Rr(ha) the risk of the 2j for i, E I, and define 24 Zieje as the difference between attributes for the pair of items selected at round = I,..,T..
hypothesis defined by hi) 1 z5j > O]. Recall that 2ij
Let 0g be the -ikeliooi estimate (MLE) fit to ł rounds of feedback, D,
0. = arg max
Σ (c. log 20) + (1- (1-c,)(1 (1 (10 2.(T2,)))
(3)
0
Let A,j lower bound the margin of comparison, (0 - 1/21 > D. for all i, E and define A, mingzj Asy/li jl. Next, let Ho( = Σ ()==0) be the Hessian of the negative log-likelihood of observations at time t under (2), given the parameter 6, also known as observed Fisher information. We define H.( == (!). For a square matrix V, we define
||>||| = Vx. Va. We make the following assumptions for our analysis:
Assumption 1. 0, satisfies ||0112 S S for some S > 0. Assumption 2. Vi E I, we have ||æ:|12 S for Q Q>00 0. Assumption 3. (fr) and (0.) have full rank and minimum eigenvalues larger than Xo > O.
Assumption I implies that 0, lies in some ball with radius S and cannot have unbounded coeffi- cients. Assumption 2 states that there exists an upper bound on the norm of the feature vectors. This assumption is trivially satisfied whenever we have a finite set of data points. Both assump- tions and 2 are standard in the bandit literature and only required for our analysis. Assumption is naturally satisfied for sufficiently large T by any sampling strategy with support on d linearly independent vectors, or can be ensured by allowing for burn-in phase of d samples. Assumption ensures the uniqueness of 0--
We start by stating the following concentration result for the deviation of Or) from the true probability (2])..). Recall that, while queries Qr (and therefore { are fixed, the stochas- ticity in the feedback e, implies that 0r and consequently (0r) are random. The proof of Lemma I is found in Appendix and builds on results for optimistic algorithms in logistic multi- armed bandits (Filippi et al., 2010; Faury et al., 2020).
Lemma (Concentration Lemma). Define, for all pairs of items i, E I, and any A > O.
2T
AT dC
Ckg (A) = exp
exp
8dC2 0r) |
| (2))
(i)(A) = exp
|Ci 12
Then, if = ai)](A), (i) and Cx, 3 S ZdT.
P (1o(=] 0.) - ol2 - 0T) )= > A) S 2dT (a: + B
Ci depends on S, Nu, Q from Assumptions 1-3 (see Appendix for definition and proof).
The concentration result in Lemma 1 is verifiable (given by observables) since the upper bound depends only the maximum likelihood estimate Or at time T, not on 6, We present sharper, unverifiable bound in Appendix C which instead depends on 9, but does not suffer from the explicit scaling with d in the definitions of a and B. The bound in Lemma I can also be expressed in terms of (Or) (,7) by using the equality ||=y || 1 (GT) |1|zy) I (0)) As long
sampling strategy
ensures that the minimum eigenvalue of (0r) does not tend to zero, i.e., the strategy is strongly consistent (Chen et al., 1999), we have aig (A.)) expl-A?,T//O (=(T))
(2Tor) )l1ay 2 " and

---

(ey(Aig) ~ expl-A., Hz,'))) Since D3 < As < 1/2 by definition, we can view a as the first-order term and /3 as the second-order term of our bound.
Lemma 1 formally captures the intuition that it should be easier to sort when annotations contain little noise, i.e., (2]]rr) small. Especially, we observe dz (T) R for pairs where A,j is suffi- ciently large, causing the first-order term to vanish, leaving us with the faster decaying second-order term 3. Lemma also tells us that the hardest pairs to guarantee a correct ordering for are the ones with both high aleatoric uncertainty under the MLE model, c.g., where annotators disagree or labels are noisy, captured by (2,, (T), as well as high epistemic uncertainty captured by ||
| H. (0r))
direct consequence of Lemma the following bound on the ordering error of ho, over I,
E[R(OT)] S 2 min {2dT (acs) (A,;) + 3xg (A:;))
n n 1)
The right-hand side in the above inequality can be bounded further by utilizing that Aij 2 ji-jjA... Together with Markov's 's inequality, this yields the following bound on P(R(OT) 2 2c).
Theorem (Upper bound on the ordering error).
Let Cx. = m Oiy ( (Ax) and 3_ maxişj Pag (Ax), with a, B from Lemma 1. Then, for a+,, 3r S 1 and any (0, 1), the ordering error R(Or) satisfies
40T
4dT ((a.- (8-1-1)-1) en (a. Ba)
4dT
P(R(OT) 2 2)
en
where oz, and B. decay exponentially with T.
Theorem 1 suggests that the probability of R(Or) 2 decays exponentially with rate that de- pends on the quantities max;,j (2, (aasyll ll, and maxi, || [1 (,,)) Both quantities are random variables that depend on the particular sampling strategy that yields Hy Focusing on the leading term, maxi, (= 0r = ir, (0,)) Theorem suggests that an active learner should gather
data to minimize this quantity and obtain the smallest possible bound. The factor || || " '(0,) is
the weighted norm of 2i w.r.t. the inverse of the observed Fisher information (cf. Kirsch and Gal (2022)). It controls the shape of the confidence ellipsoid around 0, and the width of the confidence interval around Zig. The leading term in Theorem re-scales this quantity with aleatoric noise under the MIE estimate 0y. This suggests that higher epistemic (model) certainty is needed in directions with high aleatoric uncertainty- where item similarity increases noise in comparisons.
In Appendix C.3, we comment on i) generalizations to regularized preference models, ii) applica- tions to generalized linear models with other link functions, iii) lower bounds the ordering error, and iv) an algorithm cetorrthm-sppecine -secific upper bound.
Greedy uncertainty reduction for ordering (GURO)
We present an active preference learning algorithm based on greedy minimization of the bound in Theorem 1, called GURO. We begin with fully contextual preference models of the form (0 ziz) and return Section 5.1 to parameterization variants to reduce the effects of model misspecification.
The main component of the bound in Theorem to be controlled by an active learner is the term
max o( o(=] =1))),,))))) (0,) AJEZ
which represents the highest uncertainty in the comparison of any items i,j E I under the model 0r. A smaller value of (4) yields smaller bound and stronger guarantee. Recall that, for any t = I....,,, dg is the MLE estimate of the ground-truth parameter 8, with respect to the observed history D,. Both factors in (4) are determined by the sampling strategy that yielded the item pairs (fr.j.) in Dr and, therefore, Hy and frr (the results of comparisons Cij are outside the control of the algorithm, but zij are known).
Direct minimization of (4), for subset Lp, is not feasible without access to comparisons Ciy and their likelihood under 0r. Instead, we adopt greedy, alternating approach: In each round,
5

---

Algorithm Greedy Uncertainty Reduction for Ordering (GURO), [BayesGURO]
Require: Training items Ip, attributes X (ET
1: Initialize lg
2: for I= 1, T do
3: Draw (e) based on 0r according to (5) [or (7)]
4: Observe from noisy comparison (annotator)
5:
Dj = Di-1 U (t,
6:
0,- ML)(D() according to (3) [or 0₂ MAP(D,) as in (11) in the Appendix]
7: end for
8:
Return hr
single pair is sampled for comparison by maximizing (4) under the current model estimate, and b) 0, is recomputed based on Dr Specifically, at f 1,.., ..,,,,, T, we sample,
b,, Jt arg max 622
H, (0,-))
(5)
We refer this sampling criterion as Greedy Uncertainty Reduction for Ordering (GURO), since it reduces the uncertainty of 0g in the direction of Zij- To see this, consider the change of (.,).) after single play of it, Jt- The Sherman-Morrison formula (Sherman and Morrison, 1950) yields,
H (0--1)= = H - (0--))
H (0(-1) = H (0 (2, 01-1)
(6)
+ (= 0,- |= 1| (0--)
where 21 = Zige.- With & as the second term in (6). it holds for all < j E I, with H = (f that || 1r, 1) = || H. - | S || the pair Je in (5). As Og converges to l., this pair becomes representative of the maximizer of (4) provided there is major systematic discrepancy between ID and I.
The inequality strict for
H
Surprisingly, GURO can also be justified from Bayesian analysis. Consider Bayesian model of the parameter 0 with p(0) the prior belief and p(0 Dz) the posterior after observing the preference feedback in Dr. natural active learning strategy is to sample items i for which the model preference is highly uncertain under the posterior distribution,
ie. Jt arg max Volp,-1lo(0" 24)1
i.jEIp.ic
where Volp,-, [a 2g)]] is a samite-sample estimate of the variance in predictions, computed by sampling from the posterior. In Appendix B.3, we show that the first-order Taylor expansion of the true variance is equal to the GURO criterion. Hence, we refer to sampling according to (7) as BayesGURO. Unlike GURO, BayesGURO can incorporate prior knowledge through p(0) and benefits from controlled stochasticity through the empirical estimate V, which makes it appropriate for batched algorithms deterministic criterion would construct batches of a single item pair. Both GURO and BayesGURO are presented in Algorithm 1.
Computational Complexity: Running the algorithms requires O(n²) operations each iteration to evaluate the sampling criteria (Equation 5 or 7) on all possible pairs, a problem shared by many active preference learning algorithms (Qian et al., 2015; Canal et al., 2019; Houlsby et al., 201 1). A way of mitigating this computational complexity to, at each time step, sample a fixed number of comparisons and only evaluate on these, similar to the approach taken in Canal et al. (2019). When (m). While making
sample of m < n² pairs, the complexity is reduced m too small can hurt the sample complexity, we describe in Appendix E how we implemented this sub- samplinm strategy to speed up computations in one of our experiments and observed no noticeable change in performance. Lastly, we want to highlight that in many realistic scenarios, the computational burden pales in comparison to the time takes to query an annotator.
only looking
5.1 Preference models for in- and out-of-sample ordering
Our default preference model h(i,j) = ({. > 0] is based on a fully contextual scoring function
(0)) = 0 (x4 xz2).
(8)

---

fit with a logistic likelihood of(() = p(C 1). The model's strength is that the variance in its estimates grows with d. but not with n |Z]. often resulting in quicker convergence than non-contextual methods for moderate dimension d (see, e.g. Figure 2c). The fully contextual model also generalizes to unseen items as long as the attributes for Ln span attributes observed for I.
The limitations of fully contextual model are model misspecification (error due to the functional form), and noise (error due C' not being fully determined by X). The former can be mitigated by applying the linear model to a representation function @ X > IR fo( o(z,)). A good representation o, e.g., from a foundation model, can mitigate misspecification and admit different input modalities. As demonstrated in Figure 5 in the Appendix, even a representation pre-trained for different task can perform much better than random initialization." ?
0 (ó(z;)
Noise due to insufficiencies in X cannot be mitigated by representation d(r);; If annotators con- sistently compare items based on features U not included in X, no function h(,,,,, can perfectly order the items. However, for in-sample ordering of Ip. adding per-item parameters Ç E I to the scoring function, one for each item i E Zp. can mitigate both misspecification and noise,
fe.c( xr2) - O (6(x)) o(2,)) + (c))
We call this a hybrid model and apply it in "GURO Hybrid" and baselines in experiments. The term S- Sj can correct the residual of the fully contextual model, which is small if a) the context captures the most relevant information about the ordering, and b) the functional form 0J cb(x;) is nearly well- specified. Using G - Sj alone is sufficient in-sample, but has high variance (the dimension is n instead of d) and poor generalization (G are unknown for items i & Ip). In practice, we use 1.2 regularization to prevent the model from learning an arbitrary 9 by using the full expressivity of & (see Appendix E for details). Empirically, our hybrid models exhibit the best of both worlds: When ó is poor, the model recovers and competes with non-contextual models (Figure 5); when é is good, convergence matches fully contextual models (Figure 2).
Experiments
We evaluate GURO (Algorithm 1) and GURO Hybrid (see Section 5.1) in four image ordering tasks, one with logistic (synthetic) preference feedback, and three tasks based on real-world feedback from human annotators We provide synthetic experiment in Appendix E.2 that includes empirical estimates of the bound in Theorem 1. The experiments include five diverse baseline algorithms, described next. BALD (Houlsby et al., 2011) is a priori the strongest baseline since is a contextual active learning algorithm, unlike the others. Its selection criterion greedily maximizes the decrease in posterior entropy, which amounts to reducing the epistemic uncertainty and includes a term to downplay the influence of aleatoric uncertainty. This is not always beneficial, as suggested by our analysis in Section 4, since learners may require several comparisons of high-uncertaanty pairs to get the order right. CoLSTIM (Bengs et al., 2022) is contextual bandit algorithm, developed for regret minimization and is not expected to perform well here. It included to illustrate the mismatch between regret minimization and our setting.
TrueSkill (Herbrich et al., 2006; Graepel, 2012) is a non-contextual skill-rating system that models the score of each item Gaussian distribution, disregarding item attributes, and has been adopted in various works to score items based on subjective pairwise comparisons (Larkin et al., 2022: Naik et al., 2014; Sartori et al., 2015). We use the sampling rule from Hees et al. (2016), designed for ordering. Finally, we include Uniform sampling, and to illustrate the importance of accounting for aleatoric uncertainty, we use version of GÚRO called NormMin that ignores the (2,]6)) (c) term and plays the pair maximizing || "eelll,, " i.c., it minimizes the second-orde onder term in Lemma 1. Nor- mMin corresponds the selection criterion in the concurrent work Das et al. (2024), adapted to our problem of finding the correct ordering. We refer the reader to Appendix E.2 for a detailed compar- ison where NormMin performs significantly worse than Uniform on certain problem instances, and Appendix E for details regarding the implementation and the choice of hyperparameters for GURO, BayesGURO, and baselines.
PI is feasible to update representations during exploration (Xu et al., 2022: Singh and Chakraborty, 2021). but we do not consider that here.
Our code is available at: https//gihhbb.com/Heelhyyyy/i
7

---

Unitorms
North Kendalrs Tais dieaacee
0.175
BayISUURO
0.05
0.150
BALD
CUI.SVIM
0.04
0.100
Uniform
0.075
0.02
GURO
BayesGURO
0.01
0.025
CoLSTIM
0.000
1000
0.00
500
1000
1500
2000
Compatisons
Comparisons
(a) Mean Rip with 1-sigma error region.
(b) Mcan generalization error (95% CI)
Figure 1: Xge. Performance of active sampling strategies when comparisons are simulated using a logistic model according to (2). In-sample Kendall's Tau distance RIp on 200 images (left) and generalization error Rig Ri, for models trained on 150 images and evaluated on 150 images from different distribution (right). All results are averaged over 100 different random seeds.
6.1 Ordering X-ray images under the logistic model
Our first task (X-RayAge) is to order X-ray images based on perceived age (leki al., 2022) where the preference feedback follows (well-specified) logistic model. We base this experiment on the data from the Kaggle competition "X-ray Age Prediction Challenge" (Felipe Kitamura, 2023) which contains more than 10 000 de-identified chest X-rays, along with the person's 'ss true age. Features were extracted using the 121-layer DenseNet in the TorchXray Vision package (Cohen et al., 2022) followed by PCA projection, resulting in 35 features. A ridge regression model, 0., was fit to the true age (R² se 0.67). During active learning, feedback is drawn from p(C; = 1) = a [ 2.. A), where À (set 0.1) controls the noise level. We only include the fully contextual models here since they are well-specified by design, meaning I can be ordered using only contextual features.
In the first setting. we sub-sample 200 X-ray images uniformly at random from the full set. A ground-truth ordering of these elements is derived using the learned linear model. Figure la shows the ordering етгor over 2 000 iterations. GURO and BayesGURO perform similarly, both better than the baselines. BALD starts off converging about as fast as GURO, but plateaus, most likely as a result of actively avoiding comparisons with high aleatoric uncertainty pairs where annotators disagree in their preferences. The poor performance of CoLSTIM highlights the discrepancy between regret minimization and recovering complete ordering.
In the second setting, we evaluate how well the algorithms generalize to new items. First, we sample 300 X-ray images from the full dataset. Next, we split these into two sets, with one (7p) containing the youngest 50% and the other (Tg) the oldest 50%. The algorithms were then trained to order the list containing the younger subjects, but were simultaneously evaluated on how well they could sort the list containing the older subjects. The continuously measured difference in ordering error evaluated on E and I presented in Figure lb. While all algorithms are worse at ordering items in Ig, GURO and BayesGURO achieve the lowest average difference. Together with Figure la, this means that proposed algorithms achieved the best samlee and out-of-sample sample orderings. For completeness, the in- in-sample performance of algorithms in the generalization experiment in Figure 1b are included in Appendix E.2.
6.2 Ordering items with human preference data
Next, we evaluate our algorithm three publicly available datasets to study the algorithms' per- formance when preference feedback comes from human annotators (see Table for an overview, detailed information of datasets in Appendix E. The datasets are and Ustalov, 2021), where annotators have stated which of two people appear older, ImageClarity (Zhang et al., 2016), where modified versions of the same image have been compared according to the level of distortion, as well as the extended WiscAds dataset (Carlson and Montgomery, 2017). where labels correspond to which political advertisement is perceived as more negative toward an
(Pavlichenko

---

Table 1: Datasets with preference feedback from annotators. Pretrained models are ResNet34 (He et al., 2016), all-mpnet- -a (Reimers and Gurevych, 2019), and FaceNet (Schroff et al., 2015).
Dataset
7
d
#comparisons
Data type
Embedding Model
ImageClarity
100
63
27 730
Image
ResNet34 (Imagenet)
WiscAds
935
162
9 528
Text
all-mpnet-basse -papet-
IMDB-WIKI-SHE WIKI-SBS
6072
75
110 349
Image
FaceNet (CASIA-Webfacc))
Uniform
GURO
BALD
TrueSkill
Uniform Hybrid
GURO Hybrid
BALD Hybrid
0.5
0.50
Ecror on holdout comparsion
0.4
0.075
Error Iondool compatiions
0.45
0.000
0.40
0.200
0.3
0.025
0.35
0.375
0.2-
0.30
4250
4500
4750
0.25
0.20
0.15
0
100
200
300
400
500
600
700
800
1000
2000
3000
4000
5000
Comparisons
Comparisons
(a)
ImageClarity,
100, d 63.
(h) WiseAds.
935, = 162.
0.50
0.50
Eroor on holdait comparsots
0.45
0.16
baldout compariooss
0.45
0.15
0.14
0.35
0.36
0.13
0.30
0.30
4sion spion
0.25
0.25
0.20
0.20
0.15
0.15
0.10
0.10
10000
20000
50000
10000
20000
Comparisons
Comparisous
(c) IMDE-WIKI-SBS. n. 072, d = 75.
(d) IMDB-WIKI-SbS. n = 3 000 (6 072).
The empirical error RD (h) on holdout comparison set D' when comparisons are made by human annotators. The plots are averaged over 100 (a.b) or 10 (c.d) seeds, and the shaded area represents one standard deviation above and below the mean. For every seed, 10% of comparisons were used for the holdout set. In (d) we initially order a list In of 000 images. After 10 000 comparisons the remaining 3 072 images, I Ip. are added.
Figure 2:
opponent. In all datasets, pairs of items were sampled uniformly for annotation. For each experi- ment, we construct feature vector (xx;) E IRd for all n items using a pre-trained embedding model followed by PCA, applied to reduce computational complexity. We restrict algorithms to only query pairs for which an annotation exists and remove the annotation from the pool once queried. In cases where multiple annotations exist for the same pair, the feedback is chosen randomly among these.
The images in the ImageClarity dataset have been constructed have an objective ground truth ordering but this is not the case for WiscAds or IMDB-WIKI-SbS, As the ground-truth ordering generally unknown also in real-world applications, we evaluate methods by the error on a held- set of comparisons D', (h) D E(i.,C)) [[h(i, # c). This serves as an empirical analog Kendall's Tau distance and a minimizer of Rn (h) will minimize Rz(h) for sufficiently large D', but will not converge toward 0 since there is inherent noise in annotations. This metric makes no assumptions on the ground truth ordering unlike the alternative approach of fitting an ordering all available comparisons, e.g., Maystre and Grossglauser (2017). In Appendix E.2,
1

---

we show results for the latter that highlight the limitations of estimating a "ground-truth" ordering, as well as the similar results when measuring the distance the objective ground truth ordering of the ImageClarity dataset. The longest trajectory (single seed) for any algorithm took less than 35hrs to complete on one core of an Intel Xeon Gold 6130 CPU and required at most 10 GB of memory.
In all experiments, we compare fully contextual (8) and hybrid (9) versions of GURO, BALD, and Uniform, as well as TrueSkill. The results of each experiment can be seen in Figure 2. Figure 2a shows that the ImageClarity dataset is the casiest to order using contextual (non-hybrid) features. This is expected, as features relevant to the level of distortion are low-level. In this case, the choice of adaptive strategy has a modest impact on the ordering eπror. Figures 2b and 2c highlight the differences between modeling strategies. The fully contextual algorithms initially improve rapidly, achieving rough ordering of the items, before plateauing and not making any real improvements. This indicates that the features are informative enough to roughly order the list, but insufficient for retrieving more granular ordering. The non-contextual TrueSkill converges at a much slower pace but keeps improving steadily throughout. Perhaps most interesting are the hybrid algorithms, which seemingly reap the benefits of both methods, improving as quickly as the contextual methods, but avoiding the plateau. In fact, in Figure 5 in the Appendix we show that the hybrid models perform comparably to Skil even when features are completely uninformative.
The limitations of BALD are most noticeable in the fully contextual case, where it plateaus at a higher error compared to GURO and Uniform. This is however not as prominent when we use BALD in conjunction with our hybrid model, likely a result of the increased dimensionality of the model causing BALD Hybrid to attribute more of the observed errors to model uncertainty. While this initially causes the algorithm to avoid fewer comparisons that are subject to aleatoric uncertainty, the final iterations in Figure 2c suggest that BALD Hybrid can still run into this issue given enough samples. In all experiments, GURO and GURO Hybrid perform better than or similar to our baselines, never worse. Additionally, Figures 2b and 2c showcase how our hybrid model can increase performance when used with existing sampling strategies, such as BALD or Uniform.
The final experiment, visible in Figure 2d, is few-shot scenario where after some time, additional images are added to the pool of items. of both images and comparisons. The initial pool consists of 3 000 images sampled from the dataset. After 10 000 steps, the remaining 3 072 images were added to the pool. The results again emphasize the differences between our three types of models; the increase in error of the fully contextual model very slight, likely a result of added samples being drawn from the same distribution. For TrueSkill, the eтror increases drastically as a result of the algorithm not having seen these items before and having no way of generalizing the results of previous comparisons to them. Lastly, the hybrid algorithms seem to be moderately affected. The error increases as the model has not yet tuned any of the added per-item parameters, but the extent is much smaller than for TrueSkill as the model can provide rough ranking of the out-of-sample elements using the contextual features.
was used contained the highest number
7 Conclusion
We have demonstrated the benefits of utilizing contextual features in active preference learning to efficiently order a list of items. Empirically, this leads quicker convergence, compared to non- contextual methods, and allows algorithms to generalize out-of-sample. We derived an upper bound on the ordering error and used baselines on realistic image and text ordering tasks. Both theoretical and empirical results highlight the benefit of accounting for noise in comparisons when learning from human annotators.
design an active sampling strategy that outperforms or matches
The optimality of our sampling strategy remains an open question. A future direction is to derive lower bound the ordering error, and prove an- -deellly matching bound. However, constructing upper bounds for related exed-budged tasks is an open problem (Qin, 2022). Moreover, motivated by the annotation setting, our focus has been reducing sample com- plexity and we leave it to future work to explore potential linear approximations of the sampling criteria and other trade-offs between sample complexity and computational complexity. Further, our approach can potentially be improved by performing representation learning throughout the learning process. Finally, our experiments are constrained a limited amount of already-collecte, (offline) human preference data, causing different algorithms to select disproportionately similar compar- isons. Future work should evaluate the strategies in an online setting.
geggorrthm-speeiffee upper
10

---

Acknowledgements
FDJ and HB are supported by Swedish Research Council Grant 2022-04748, FDJ is also supported in part by the Wallenberg AI, Autonomous Systems and Software Program founded by the Knut and ALice Wallenberg Foundation. EC and DD are supported by Chalmers Al Research Centre (CHAIR). The computations were enabled by resources provided by the National Academic Infras- tructure for Supercomputing in Sweden (NAISS), partially funded by the Swedish Research Council through grant agreement no. 2022-06725.
References
Nir Ailon. Active learning ranking from pairwise preferences with almost optimal query complexity. Advances in Neural Information Processing Systems, 24, 2011.
Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, Carol Chen, Catherine Ols- son, Christopher Olah, Danny Hernandez, Dawn Drain, Deep Ganguli, Dustin Li, Eli Tran- Johnson, Ethan Perez, Jamie Kerr, Jared Mueller, Jeffrey Ladish, Joshua Landau, Kamal Ndousse, Kamile Lukosuite, Liane Lovitt, Michael Sellitto, Nelson Elhage, Nicholas Schiefer, Noemi Mer- cado, Nova DasSarma, Robert Lasenby, Robin Larson, Sam Ringer, Scott Johnston, Shauna Kravec, Sheer El Showk, Stanislav Fort, Tamera Lanham, Timothy Telleen-Lawton, Tom Con- erly. Tom Henighan, Tristan Hume, Samuel R. Bowman, Zac Saffield-Dodde Ben Mann, Dario Amodei, Nicholas Joseph, Sam McCandlish, Tom Brown, and Jared Kaplan. Constitutional ai: Harmlessness from ai feedback, 2022.
Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi Paull and Eyke Hüllermeier. Preference-basee online learning with dueling bandits: A survey. The Journal of Machine Learning Research, 22 (1):278-385 2021.
Viktor Bengs, Aadirupa Saha, and Eyke Hüllermeier. Stochastic contextual dueling bandits under linear stochastic transitivity models. In International Conference on Machine Learning, pages 1764-1786. PMLR, 2022.
Christopher M Bishop and Nasser M Nasrabadi. Springer, 2006.
Pallern recognition and machine learning.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324-35,, 1952.
Klaus Brinker. Active learning of label ranking functions. In Proceedings of the twenty-first inter- national conference on Machine learning. page 17, 2004.
Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hul- lender. Learning to rank using gradient descent. In Proceedings of the 22nd international confer- ence on Machine learning, pages 89-96, 2005.
Ludwig M. Busse, Morteza Haghir Chehreghani, and Joachim M. Buhmann. The information con- tent in sorting algorithms. In 2012 IEEE International Symposium Information Theory Pro- ceedings, pages 2746-2750, 2012. doi: 10.1109/SSTT22022224400.
Gregory Canal, Andy Massimino, Mark Davenport, and Christopher Rozell. Active embedding search via noisy paired comparisons. In International Conference on Machine Learning, pages 902-911. PMLR, 2019.
David Carlson and Jacob M. Montgomery. A Pairwise Comparison Framework for Fast, Flexible, and Reliable Human Coding of Political Texts. American Political Science Review, 111 843, November 2017. ISSN 0003-0554, 1537-5943.
Kani Chen, Inchi Hu, and Zhiliang Ying. Strong consistency of maximum quasi-likelihood estima- tors generalized linear models with fixed and adaptive designs. The Annals of Statistics, 27(4): 1155-1163, 1999.
11

---

Xi Chen, Paul N. Bennett, Kevyn Collins- Collins-Thompson and Eric Horvitz. Pairwise ranking aggrega- tion crowdsourced setting. Proceedings of the sixth ACM international conference on Web search and data mining, WSDM '13, pages 193-202, New York, NY, USA, February 2013. As- sociation for Computing Machinery. ISBN 1--5--3--86694 doi: 10. 00.1144443333962433422 2433440
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances neural information processing sys- tems, 30, 2017.
Wei Chu and Zoubin Ghahramani. Preference learning with gaussian processes. In Proceedings of the 22nd international conference on Machine learning, pages 137-144, 2005.
Joseph Paul Cohen, Joseph D. Viviano, Paul Bertin, Paul Morrison, Parsa Torabian, Matteo Guar- rera, Matthew P Lungren, Akshay Chaudhari, Rupert Brooks, Mohammad Hashir, and Hadrien Bertrand. TorchXRay Vision: A library of chest X-ray datasets and models. In Medical Imaging with Deep Learning, 2022.
Nirjhar Das, Souradip Chakraborty, Aldo Pacchiano, and Sayak Ray Chowdhury. Provably sample efficient rihf via active preference optimization. arXiv preprint arXiv:2402. 10500, 2024.
Victor H. de la Peña, Michael J.
Klass, and Tze Leung Lai. Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws. The Annals of Probability, 32(3):1902 - 19933, 2004. doi: (01121/4/00911944000000
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-24882 255. Icce, 2009.
Qiwei Di, Tao Jin, Yue Wu, Heyang Zhao, Farzad Farnoud, and Quanquan Gu. Variance-awan regret bounds for stochastic contextual dueling bandits. arXiv preprint arXiv:2310.00900 2023.
Miroslav Dudík, Katja Hofmann, Robert E Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Con-
textual dueling bandits. In Conference on Learning Theory, pages 563-587. PMLR, 2015.
Boli Fang. Fixed- Fixed-budget budget pure exploration in multinomial logit bandits. In International Joint Con- ference on Artificial Intelligence, 2022.
Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algo- rithms for logistic bandits. In International Conference on Machine Learning, pages 3052-3060. PMLR, 2020.
Paulo Kuriki Felipe Kitamura, Lilian Mallagoli. Spr x-ray age prediction challenge, 2023.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In J. Lafferty, C. Williams, J. Shawe-Taylos R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23, Curran Associates, Inc., 2010.
Johannes Fürnkranz and Eyke Hüllermeier. Pairwise preference learning and ranking. In European conference on machine learning, pages 145-156. Springer, 2003.
Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998- 19277 PMLR, 2016.
Anne-Marie George and Christos Dimitrakakis. Eliciting kemeny rankings, 2023.
Thore Graepel. Score-based bayesian skill learning. Proceedings of the European Confer- ence Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD-D) 12), January 2012.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778. IEFF, 2016
12

---

Reinhard Heckel, Max Simchowitz, Kannan Ramchandran, and Martin Wainwright. Approximate ranking from pairwise comparisons. In International Conference on Artificial Intelligence and Statistics, pages 1057-1066. PMLR, 2018.
Jöm Hees, Benjamin Adrian, Ralf Biedert, Thomas Roth-Berghofer, and Andreas Dengel. Tssort: Probabilistic noise resistant sorting. arXiv preprint arXiv:1606.05220 2016.
Ralf Herbrich, Tom Minka, and Thore Graepel. TrueskillTM; a bayesian skill rating system. Advances in neural information processing systems, 19, 2006.
Neil Houlsby, Ferenc Huszár, Zoubin Ghahramani, and Máté Lengyel. Bayesian Active Learning for Classification and Preference Learning, December 2011. 11Xiv:1112.5745 [cs, stat].
Hirotaka leki, Kaoru Ito, Mike Saji, Rei Kawakami, Yuji Nagatomo, Kaori Takada, Toshiya Kariyasu, Haruhiko Machida, Satoshi Koyama, Hiroki Yoshida, Ryo Kurosawa, Hiroshi Mat- sunaga, Kazuo Miyazawa, Kouichi Ozaki, Yoshihiro Onouchi, Susumu Katsushika, Ryo Mat- suoka, Hiroki Shinohara, Toshihiro Yamaguchi, Satoshi Kodera, Yasutomi Higashikuni, Kat- suhito Fujiu, Hiroshi Akazawa, Nobuo Iguchi, Mitsuaki Isobe, Tsutomu Yoshikawa, and Is- sei Komuro. Deep learning-basee age estimation from chest X-rays indicates cardiovascular prognosis. Communications Medicine, 2(1):1-12, December 2022. ISSN 2730-664X. doi: 10. 00.10088/433360022000222 Number: I Publisher: Nature Publishing Group.
Kevin Jamieson and Robert Nowak. Active ranking using pairwise comparisons. Advances in neural information processing systems, 24, 2011.
Ikbeom Jang, Garrison Danley, Ken Chang, and Jayashree Kalpathy-Cramer, Decreasing annotation burden of pairwise comparisons with human-in-the-loop sorting: Application in medical image artifact rating. arXiv preprint arXiv:2202.0483 2022.
Kwang-Sune Jun, Lalit Jain, Blake Mason, and Houssam Nassif. Improved confidence bounds for the linear logistic model and applications to bandits. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceed- ings of Machine Learning Research, pages 5148-5157. PMLR, 18-24 Jul 2021.
Maurice George Kendall. Rank correlation methods. Griffin, 1948.
Andreas Kirsch and Yarin Gal. Unifying approaches in active learning and active sampling via fisher information and information-theeee 2022. ISSN 2835-8856. Expert Certification.
quantities. Transactions on Machine Learning Research,
Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration in generalized linear bandits. In International Confer- on Artificial Intelligence and Statistics, pages 2066-2076. PMLR, 2020.
Andrew Larkin, Ajay Krishna, Lizhong Chen, Ofer Amram, Ally R. Avery, Glen E. Duncan, and Perry Hystad. Measuring and modelling perceptions of the built environment for epidemiological research using crowd-sourcing and image-based deep learning models. Journal of Exposure Sci- ence & Environmental Epidemiology, 3926),892-899, November 2022. ISSN 1559-064X. doi: 10. 10.10388441370-022-00444 8. Number: 6 Publisher: Nature Publishing Group.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020. doi: 10. 108571401.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear con- textual bandits. In International Conference on Machine Learning, pages 2071-2080. PMLR. 2017.
Mats Lidén, Antoine Spahr, Ola Hjelmgren, Simone Bendazzoli, Josefin Sundh, Magnus Sköld, Göran Bergström, Chunliang Wang, and Per Thunberg. Machine learning slice-wise whole-lung CT emphysema score correlates with airway obstruction. European Radiology, 34(1):39-49, January 2024. ISSN 1432-1084. doi: 10. 10.1007760033-002-098333
13

---

Suiyi Ling, Jing Li, Anne Flore Perrin, Zhi Li, Lukáš Krasula, and Patrick Le Callet. Strat- egy for boosting pair comparison and improving quality assessment accuracy. arXiv preprint NNNv:201000003700 2020.
Bo Long, Olivier Chapelle, Ya Zhang. Yi Chang, Zhaohui Zheng, and Belle Tseng. Active learning for ranking through expected loss optimization. In Proceedings of the 33rd international ACM SIGIR conference on Research and development in information retrieval, pages 267-274, 2010.
Hao Lou, Tao Jin, Yue Wu, Pan Xu, Quanquan Gu, and Farzad Farnoud. Active ranking without strong stochastic transitivity. Advances in neural information processing systems, 35:297-309, 2022.
Andrew K Massimino and Mark A Davenport. As you like it: Localization via paired comparisons. Journal of Machine Learning Research, 22(186):1 2021.
Lucas Maystre and Matthias Grossglauser. Just sort it! a simple and effective approach to ac- tive preference learning. In International Conference on Machine Learning, pages 2344-2353.
PMLR, 2017.
Viraj Mehta, Vikramjeet Das, Ojash Neopane, Yijia Dai, Ilija Bogunovic, Jeff Schneider, and Willie Neiswanger. Sample efficient reinforcement learning from human feedback via active exploration. arXiv preprint arXiv:23/2.00000 2023.
Tom Minka, Ryan Cleven, and Yordan Zaykov. Trueskill 2: An improved bayesian skill rating system. Technical Report, 2018.
Subhojyoti Mukherjee, Anusha Lalitha, Kousha Kalantari, Aniket Deshmukh, Ge Liu, Yifei Ma, and Branislav Kveton. Optimal design for human feedback, 2024.
Nikhil Naik, Jade Philipoom, Ramesh Raskar, and César Hidalgo. Streetscore-predicting the per- ceived safety of one million streetscapes. In Proceedings of the IEEE conference on computer vision and pattern recognition workshops, pages 779-785, 2014.
IFD Oliveira, S Zehavi, and O Davidov. Stochastic transitivity: Axioms and models. Journal of Mathematical Psychology, 85:25-35, 2018.
Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal. Katarina Slama, Alex Ray. John Schulman, Jacob Hilton, Fraser Kel- ton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder. Paul Christiano, Jan Leike, and Ryan Lowe. Training language models follow instructions with human feedback, 2022.
Nikita Pavlichenko and Dmitry Ustalov. Imdi--iki-sbs: An evaluation dataset for crowdsourced pairwise comparisons. CoRR, abs/21 14990, 2021.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-leamn: Machine learning in Python. Journal of Machine Learning Research, 0122825-8800 2011.
Andrew S. Phelps, David M. Naeger, Jesse L. Courtier, Jack W. Lambert, Peter A. Marcovici, Javier E. Villanueva-Meyer, and John D. MacKenzie. Pairwise comparison versus Likert scale for biomedical image assessment. AJR. American journal of roenigenology, 204(1):8-14, 2015. ISSN 0361-803X. doi: 10.22 1122114/jr.144 14.13022.
Li Qian, Jinyang Gao, and HV Jagadish. Learning user preferences by adaptive pairwise comparison. Proceedings of the VLDB Endowment, 8(1 I): 11:1-13-1333, 2015.
Chao Qin. Open problem: Optimal best arm identification with fixed-budget. In Conference on Learning Theory, pages 5650-5654. PMLR,, 2022.
Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert- networks. In Proceedings of the 2019 Conference on Empiricul Methods in Natural Language Processing. Association for Computational Linguistics, 11 2019. URL. https: / //trx//xvv.v///////////.v//aav .rr// abs/1908. 10084.
14

---

Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Operations Research, 35(2):395-411 2010.
Mathematics of
Aadirupa Saha. Optimal algorithms for stochastic contextual preference bandits. Advances in Neural Information Processing Systems, 34:30050-30062 2021.
Aadirupa Saha and Akshay Krishnamurthy. Efficient and optimal algorithms for contextual dueling bandits under realizability. In International Conference Algorithmic Learning Theory, pages 968-994, PMLR, 2022.
Andreza Sartori, Victoria Yanulevskaya, Almila Akdag Salah, Jasper Uijlings, Elia Bruni, and Nicu Sebe. Affective analysis of professional and amateur abstract paintings using statistical analysis and art theory. ACM Transactions on Interactive Intelligent Systems (TiiS), 5(2):1-27, 2015.
Florian Schroff, Dmitry Kalenichenko, and James Philbin. FaceNet: A Unified Embedding for Face Recognition and Clustering. In 2015 JEEE Conference on Computer Vision and Pattern Recogni- fion (CVPR), pages 815 823, June 2015. doi: 10. 2009//CV..211..72966666. [es].
arXiv:1503.03832
Jack Sherman and Winifred J. Morrison. Adjustment of Inverse Matrix Corresponding to Change One Element of a Given Matrix. The Annals of Mathematical Statistics, 21(1):124 127, 1950. doi: 10.1214/aoms/ 1777299897777
Rodrigo M Silva, Marcos A Gonçalves, and Adriano Veloso. A two-stage active learning method for learning to rank. Journal of the Association for Information Science and Technology. 65(1): 109-128, 2014.
Max Simchowitz, Kevin Jamieson, and Benjamin Recht. The simulator: Understanding adaptive sampling in the Inderate-confidena regime. In Satyen Kale and Ohad Shamir, editors, Pro- ceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 1794-1834, PMLR, 07-10 Jul 2017. URL httpa://proceedingg: mlr. S.l..press/v5////.. http:////ssccnoiiiiiiiiieeme html.
Ankita Singh and Shayok Chakraborty. Deep active learning with relative label feedback: An ap- plication to facial age estimation. In 2021 International Joint Conference on Neural Networks (IJCNN) pages 1-8. IEEE, 2021.
Hanna Tärnásen and Herman Bergström. Rank based annotation system for supervised learning in medical imaging. Master's thesis, Chalmers University of Technology, 2023.
Dmitry Ustalov, Nikita Pavlichenko, and Boris Tseitlin. Learning from Crowds with Crowd- Kit. Journal of Open Source Software, 9(9)):2277, 2024. ISSN 2475-9066 doi: 105//00s..06220
Tianhao Wu, Banghua Zhu, Ruoyu Zhang. Zhaojin Wen, Kannan Ramchandran, and Jiantao Jiao.
Pairwise proximal policy optimization: Harnessing relative feedback for Ilm alignment, 2023a.
Yue Wu, Tao Jin, Hao Lou, Farzad Farnoud, and Quanquan Gu. Borda regret minimization for generalized linear dueling bandits. arXiv preprint arXiv:2303 08816, 2023b.
Pan Xu, Zheng Wen, Handong Zhao, and Quanquan Gu. Neural contextual bandits with deep representation and shallow exploration. In International Conference Learning Representations, 2022.
Xinyi Yan, Chengxi Luo, Charles LA Clarke, Nick Craswell, Ellen M Voorhees, and Pablo Castells. Human preferences ducling bandits. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 567-577 2022.
Miao Yang, Ge Yin, Yixiang Du, and Zhiqiang Wei. Pair comparison based progressive subjective quality ranking for underwater images. Signal Processing: Image Communication, 99:1 16444, 11 2021. ISSN 09235965. doi: 10.
Georgios Yannakakis and Héctor Martínez. Ratings are overrated! Frontiers ICT, 2, July 2015. doi: 10.3389/fct.2011.00001
15

---

Yisong Yue and Thorsten Joachims. dueling bandits problem. Proceedings of the 26th Annual International Conference on Machine Learning, pages 1201-1208, 2009.
Interactively optimizing information retrieval systems
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, ((15):1338-1550 2012.
Xiaohang Zhang, Guoliang Li, and Jianhua Feng. Crowdsourced top-k algorithms: an experi- mental evaluation. Proceedings of the VLDB Endowment, 9(8):612-b) 623, April 2016. ISSN 2150-8097. doi: 10.14778/922558222215555 URL https: //ll. acm org/ 14778/ 2921558. 2921559.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 43037-43061 PMLR, 23-29 Jul 2023.
16

---

A Notation
Table 2: Notation
I
Collection items I {I, n)
Number of items
d
Dimension of item attributes
2j E Rd
Context attributes for item
20 E R
Rig 2, Ij for i.j I
Score for item E I The outcome of the comparison at time i, if in preferred to je
1)
D:
D, = ((11, cı)..., (i,, (4)
O E IR
Model parameter
O, E Rd
Model parameter of the environment Estimated parameter at time Sigmoid (logistic) function derivative of (-)
0, R
o()
o()
H2(0)
Hessian of the negative log-likelihood H, = Σ 2)
H2(0)
Hessian normalized by number of plays :0) (.)
OB. Rd
The MAP estimate of 0 at time t
H
The Hessian in the Bayesian setting, adjusted by the prior covariance H H
|ay H. (0)
|
H. (0)
S
S: E Es where e, C.
(=T0.)
h
Comparison model (binary output)
f
Comparison logit (typically linear), e.g., fo = T (x: - xz)) An upper bound on the norm of 0s, that is |10.12 S S
S
17

---

B Algorithms
B11 MLE estimator for logistic regression
The log-likelihood (,) of data D, (( with Ii, -ist under logistic regression model with parameters is defined by
Lx(0) = Σ co log log ) c.) a(0 -0))))))
The maximum likelihond estimator (MI.) time is the parameters
arg max L.(
(10)
The regularized estimator with ridge/&z penalty with parameter À
0. = arg min L, (0) + 1110
B.2 Bayesian estimator for logistic regression
B, is the MAP estimate of at time according the log likelihood
B, = arg max In p(0 Dz),
(11)
where
In p(0) D.)
B.,0)
Hg. 08.0)
+
Σ a In(o In(o((T),))) 0)) + (1 a) In(1 ( 01) + const.
The hessian at time is defined
Ha. H + Σ d(zI,0B.))Lg HE H..
(bJ)ED:
Moreover, if priors 03.0 and H
Ia are used, log likelihood boils down to:
In | D.) = 11012 +
- In(o(=),), 0)) + +1 a)) In(1 - (zI + const
which implies that the MAP estimate will same as MLE estimate with ridge regularisation frequentist setting. Similarly, the Hessian becomes:
Ha. H. + la
Sequential updates are also possible in the Bayesian setting by using your current estimates as the new priors. Note that this will give slightly different results, as the calculation of Hæ, depends on the current estimate of 0g.1-
B.3 Stochastic Bayesian uncertainty reduction (BayesGURO)
We describe BayesGURO, Bayesian sampling criterion, closely related to GURO. Consider Bayesian model of the parameter 0 with p(0) the prior belief and p(0 D.) the posterior after observing the preference feedback in D.. natural strategy for learning posterior variance predictions for their comparison,
about the ordering of I is to sample items it. Je based estimate
ic, J:
arg VoID, 10 2,y)]
(12)
Here, Vo D, [0" 2;z]] is estimate of the variance of probabilities a0" 25j). computed from finite samples drawn from posterior and ii) induces controlled stochasticity in the selection of item pairs. This can useful in batched learning settings so that multiple pairs can be sampled within the same batch. A deterministic criterion would return the same item pair every time until 0 is updated. We refer to the sampling criterion in (7) as BayesGURO.
Estimating variance this way i) allows for tractable implementation.
18

---

For the logistic model considered in Section 4, using Laplace approximation with Normal prior (0, H on 0, the Bayesian criterion in (7) related the GURO sampling criterion in (5) through the first-order Taylor expansion of the variance:
Val, (a(0' zn))) (a 10" =.)l)) [0' (0"=z)) zu3 (d+ (d(0 (gg
where 8 is the MAP estimate of at and H the Hessian adjusted by prior covariance H g.o (further described in Appendix B.2). Thus, to a first-order approximation, for a large number of posterior samples, the GURO and BayesGURO active learning criteria are equivalent, save for the influence of the prior. In practice, we find that the Bayesian variant lends itself well to sequential updates of the posterior. The choice of prior p(0), which could be useful under strong domain knowledge, and the stochasticity of using few posterior samples to approximate make the two criteria distinct.
B.4 Uniform sampling
The uniform sampling algorithm is given in Algorithm 2. The corresponding Bayesian version replaces line with the MAP estimate.
Algorithm 2 Uniform sampling algorithm
Require: Training items Ip, attributes X (ez
1: for = -..... T' do
2: Sample (ie. Jt) uniformly
3: Observe from noisy comparison (annotator)
4: D: D fe,
5: Let 82 = MLE((D,)
6: end for
7:
Return hT
B.5 BALD
Algorithm BALD bandit
Require: Training items Ip. attributes X = (xi Initialize 8,0
H = X A-1
2: for == 1, .... T do
3: Draw (e) = arg max; Hly 2i,j, D.-1] E
1fl 2i.j, 8]
4: Observe from noisy comparison (annotator)
5: D; = D.-1 (e,,
6:
Let 02 = MAP(Dd)
7: Update H + HB + E(S)ED, ((2T,00)2,,2))
8: end for
9:
Return hT
Where the posterior is calculated as in Appendix B.2 and Mly zigs Dz-1] Be- W =s.s, 0] is approximated as in Appendix B.5.1.
B.5.1 Deriving the BALD sampling criterion
The BALD criteria formalized using our notation becomes
arg max Hyy Zi.j. Dr) - Eo-pio [H s.,, Ø]],
where H/ represents Shannon's entropy
h(p) - -pgg - logg p).
The first term of the equation becomes
19

---

Hly Ziy, D.] h(Pr(y) Pi.. D.)) = (frrev) 5) Di)dd)
Here Pr(y Zigy D.) is predictive distribution for our Bayesian logistic regression model. As covered Bishop and Nasrabadi (2006, Chapter 4), this expectation cannot be evaluated analytically but can be approxi- mated using the probit function 4;
0 22.
0 2 =1|=,
Pr(y zu, D.) = +
2
A-2 + |is
H, (0.)
Next, the term Eo D.) [Hly zeg, 0]] must be calculated. The true definition is
Ea-ptena [H Ze... 0]] = f 1(0000 a.)))a(( Oc, H, )d0.
To make this variable integral, let X 0 zi,5 define random variable. Since 0 A(,,,, H, ") and Ziy just constant vector, we know that will follow a univariate normal distribution N(0, Rug I1, This allows to rewrite the integral
f Mo(("" 2))
/ h((())))N( zi.s || (1
H, H,')
However, this integral has no closed form solution. Instead we perform the same strategy as in Houlsby et al. (2011) and do Taylor expansion of In ( z)). The third-order Taylor expansion gives
x
(((()) 2 exp
81n
Inserting this, the term can approximated
/ h(o(z)))((z 00 Wلا, )dx
(-
(-
x²
exp
(-8m2 81n2
N(x
10, 21.1 ||21z] || )d
C
(0, zi,} C2)
||, 12 +
C2
exp
- Ris H,
where C = 1n Finally, we arrive at an estimation of the objective function we wish to maximize:
Hly 245, Dr) B2) Hly 2i.; 8]] h (o
0g z
112
HI,"
(0 22,,)²
/
/
C
exp
(1| 1|2
H. + C2)
H,
20

---

Proofs of Lemma and Theorem
C.1
Proof of Lemma
Proof. We now proceed bound, under Assumptions 1-3 w.r.t time
P (lo(2]00)) -((,0)1 2)-
From the self-concordant property of logistic regression have (Faury al., 2020)
(e) 0..) ((z T0:) 0.)1 1 12, (0: 0.)1
1
(13)
will prove a high probability bound on the event
22)6 a-)l + 4 10, (0.-0-))) 0.)1 <
(14)
Directly trying bound the LHS in Equation 14 will result in rather messy expression. Instead, define the events
& 0z2 -0.-0.) 0.) -
& =
1 10 -0)1 - 2
0.)1
A
Clearly & U implies the expression in Equation 14. Assume we have bounds the complement of these events, ((f)) and P (ES) S B. Then
P (10(=)00)-0((3001) > 2) + 0,8
S 2a 23.
We now praceed to hound the probability of these complements separately.
Step 1. Relating 9 to 0:: The first challenge in our analysis to is relate 0, and 0.. In contrast to linear regression. where we have closed-forn expression for 0,, there is no analytical solution for 0, given set of observation. However, know that 0, is the MLE, corresponding
0, = arg max (0)
where
L( Σ log (x (1 cc, log (1 -2.00 (z]o))
We have
Vol=(0))
c.
Σ
1=1 s=1
(P)
hence go.).) = E.=r C.
standard trick logistic bandits (Filippi et al., 2010: Faury al., 2020: al., 2021) relate 0, 0, to ge (0.) - ge (0.). Especially, the following equality is due to the mean-value theorem (see Filippi et al. (2010)
ge(O.)) ((,)) H, (8') (0_ 0c)
(15)
where 8' is some convex combination of 0,, dc. Note that (0') has full rank.
Using Equation 15 yields
2. (0. - -6:)
2 H, (0') (g. (x())))
Furthermore, since g(.)) Ei=r CaZo, due VoL.(A.) we have
: (0.) (0.) = Σ
2 0.
21

---

where is a sub-Gaussian random variable with mean 0 and variance =z oz. We define
S
Σ Ca
We now have
Fiy (0. 01)
2 T
Hi (0')S:
and Lemma in Faury et al. (2020) states that H,
(8') (1 25) (0.) where |00.12 S. Hence,
Bi (0. - 0.) - (1+
2ng H H,,)),),,
Step 2. Tail bound for vector-valued martingales:
We will now prove an upper bound on the probability that 2 H (9-)). deviates much from a certain threshold. This step is based on the proof of Lemma in Filippi et al. (2010) which itself is based on derivation of concentration inequality in Rusmevichientong and Tsitsiklis (2010). The difference compared Filippi al. (2010) is that work with the Hessian H, (0.) instead of the design matrix for linear regression Vi = Σ, v. This require us to construct slightly different martingale.
Let A and B are two random variables such that
2- B² 2
I
74
ER
(16)
then due to Corollary 2.2 in de la Peña et al. (2004) holds that Vo v2 and > 0
B2 b
+1 11))
S exp {
-a²
p [A] 2 / (B² + b)
1 2
log
(17)
2
Let R and consider the process
(0.. = exp {mi
Tw s, > ?(llvll
(18)
will now proceed to prove that Mf (0, 77 is a nen-negative super martingale satisfying Equation 16. Note that
nn S. - 721101
Σ m zuc, - 3(0 o(0 zn)? (1' (n=za))
22)
Σ F.
Further use the fact that es is sub-uuubsees Gaussian with parameter V., i.c.
x s exp (1²x*), ,x
Let D.-1 denote the observations up until time then
E [exp(F.) D.-1] =
exp
2q
exp
5(0% 2.)
11
I exp {u?X} exp ( (-v32²} =1.
This also implies
[M7 Da-1l S &MT,((0,7))
and (0., 1)) is super-martingale satisfying
E [exp pm T S. - - (imllin))
H 1, 2
and apply the results of de Peña al. (2004).
now follow the step of the proof of Lemma in Filippi al. (2010). let / log for some 8 E (0, 1/e) and let b = >o1ln113 We have with probability at least - 5
I
|| Inllaa.ee>) Ao molml
))
In Sel i v 2200 8
||l
1+ log 1+
(o
22

---

Rearanging and using the fact that Ao 1ol1v & Iblli S 4lllll yields
In Stl S p(>o)] vn (..0)) 2log 8
(19)
where p defined
1+ 104)
p(>a) = 1/3+ log
Au
We take M, be matrix such that M2- (0.) and that for any 0
P (ISS,) (0.) dr Σ P St Mr es 27)
where is the i:th unit vector. Equation 19 with M, together with | the following holds with with probability at least -
= yield that
| ((o.) S ((Ao) 2d log log d
(20)
Step 3. (Unverifiable) High-probability bounds on E and E2.
We now have enough machinery to state high- probb-bbbbbblity bounds for our two events. These bounds will be unverifiable in the sense that the depend on the true parameter A. which is not known us during runtime. We derive verifiable bounds in the next step the proof.
Recall that H, (0.) is symmetric. We apply Equation 19 with 7 H, (0.) and 0 in place of 8. First, we note that ||H," (0. (..)) (o.)) = || ((..) which implies with probability at least 1 a
H. (0.)S: = |. H. H0HH''0,. (0.)). p(Ao))lzullly (0, 2
22
(21)
We solve for smallest possible E (0, such that
i S 2
A
(1 (1+2
(.)
2
Rearanging yields
-A2
S exp
+ log l
(22)
8Ao())) + 25)²
For Ea and the bound on its probability.
9 > we have
1 1
0.) < 1 || ",, (2))) log 1 A
2
and
B < exp (1)00(1--5) (122)11177000)))
logt
(23)
Note that both Equation 22 and Equation 23 under the assumption that the RHS satisfy 1/e since this required in order to apply the results are approaching zero as ((te "), ignoring various constants, for reasonable sampling strategies and will satisfy this condition eventually.
Peña et al. (2004). As we discuss in the main text, these quantities
Step 4. (Verifiable) brobbbprobbbility bounds on E and &,.
The bounds in the previous step depend the parameter 0. which do not have access in practice. We again use Lemma 10 of Faury (2020) together with Sauchy-Schwarde
10 0.)1 = H. (2')0
< (1 + 25) By |1E,, (00 || 11E "(0_)"
23

---

Connecting to Equation (13), we have
(o(2 o 02) s 10)) 0.)1 | (0+ 0-3l"
s 50(4.0011 25) وما | ( || Sz ( (0-) + + 25) الاا (
Using Equation 20, and the fact that all terms are strictly greater than 0, we have with probability at least
d h2d 2d log /V log
(1 (1+25)6(2))0) | 2 (I | (e,) (1
(24)
We solve for smallest a E (1/e) such that Equation 24 is smaller than A1./2. This yields
-
S exp
+ log dt
(do) 25)² (H(2))))l=oll
Same steps for |8 yields
-A
8 exp
log dl
(p)( + 25)²
(12w)lle)
For brevity, define C1 = (1 + 25)
Using the definition of H, yields the statement of Lemma 1.
C.2 Proof of Theorem
Proof. We let > denote that is preferred to j. W.l.o.g assume > 2 > > n. The key observation is thatfor any and j such that i < j holds that
A (j - i)
If we get the wrong relation between i, then a (2] o(2]]0r) 0r) > (j i)A.. Lemma I implies
-
Plo(=])0) > G 1)4) s (exp
8d) + 25)² (o(=T0r) Or) - o (0r)))
i)- (1 || (bT))
+ exp
dp(>a)(1 + 25)²
8
Let R(Or) be the ordering error the items. Then, under uniform distribution over items we have
E[R(OT)]
4df v(n 1)
ΣΣ =
gi-i
(25)
E= j=it1
A and B will be upper bounded using the argument. We upper bound A

---

-
Let 0. == exp
then
8dC1 maxi, o(z1g 1
H (0.)
(0o)
1 n-1 n
a i- S (n-1)
n Σ
Eai-1)
i=1 1=i+1
1=0
S (n 1)
This follows from the definition of ,1,- and properties of the geometric sum. It is easy to see that 1- -1 Hence,
4dT
4dT
(a,
- -1)
n1
{
we perform the same steps with 3. = exp
00; maxi,
| 11 2T (0.)
10 get
4df
4df
(g.² 1 1)
n(n
Combing yields and
E
[R((T)]
<
4dT
((ai' + +3.5 - -1) -1)-
n
By Markov's inequality have
P(R(OT) 2 < 1dT
1) -1a + (0. 18) -1)
(26)
n
C.3 Extensions current theory
Regularized estimators. In our analysis in Section 4, we have assumed that 0y is the maximum like- lihood estimate and that H(Or) has full rank. This can be relaxed by considering & (Ridge) regularization where Oxo.7 is the optimum of the regularized log-like log-likeldhood with regularization Aol and HAg (0xo.r) Er dz. 0xo. = + Apl. The same machinery used to prove Lemma (Filippi et al., 2010; Faury et al., 2020) can be applied this regularized version with small changes the final bound.
Generalized linear models. It is also possible to derive similar results for generalized linear models with other link functions, (==]000), by using the general inequality H(0) 2 x "V with = Σ =.2, and x. 2 1/ min.,, 0.2,50.). We conjecture that this will yield a scaling of ~ exp(-A2TT// where, unfortunately, might be very large. For a more thorough discussion on the dependence on x in generalized linear bandits, see Lattimore and Szepesvári (2020. Chapter 19).
Lower and algorithm-speeificc upper bounds on the ordering error. A worst-case lower bound on the ordering error be constructed in the fixed-confidence setting, where the goal is to minimize the number of comparisons until correct ordering found with given confidence, by following Garivier and Kaufmann (2016). This involves defining set alternative models Alt(0.) which differs from 0. their induced ordering of Z. The bound is then constructed by optimizing the frequency of comparisons of each pair of items so that such alternative models are distinguished as much as possible from the true parameter. We have left this result of the paper Simchowitz et (2017) for a discussion on the limitations of these asymptotic results in the standard bandit setting). Constructing lower bound for our fixed- bbdget setting, of learning as good an ordering as possible with a fixed number of comparisons, is much more challenging. The fixed-confidence result yields bound for the fixed-budget case (Garivier and Kaufmann, 2016), but constructing either tight lower bound or tight algorithm-specific upper bound open problem (Fang, 2022).
find it uninformative in the regime when the number of comparisons is small, (see
25

---

D Comparison with regret minimization
Bengs et al. (2022) considered problem formulation where the goal is to learn parameter which determines the utility Y1. for arms I,..., function of observed context vectors 24,t sequence of rounds t 1,
armss
Y,, 20=00x Xx,
The probability that item is preferred over (denoted i j) in round t is decided through comparison function F.
Pr(i > j Xx,e) = F(Y Yi,t)
The goal in their setting is to, in each round, select two items (ie, so that their maximum (or average) utility is as close as possible to the utility of the best item. The expected regret in their average-utility setting is
RBSH B BIE
Yu,: Yse.)).
Proposition 1 (Informal). An algorithm which achieves minimal regret in the setting of Bengs al. (2022) can perform arbitrarily poorly in setting.
Proof. optimal choice arm pair BSH setting the optimal and next-optimal arm (x7. x)) such that ? > & > j for any other arms j. Assume that the ordering all other arms is determined by a feature (K) but that (k) = X (k).. Then, no knowledge will be gained about arms other than the top choices under the BSH regret. the number of arms grows larger, the error in our setting grows as well.
Saha (2021) study the same average-utility regret setting and give lower bound under Gumbel noise. Saha and Krishnamurthy (2022) investigated where there is computationally efficient algorithm that achieves the derived optimality guarantee.
26

---

E Experiment details
For BayesGURO and BALD, the postcrior p(0 Dz) is estimated using the Laplace approximation as described in Bishop and Nasrabadi (2006, Chapter 4). With this approximation, the covariance matrix is the same as the inverse of the Hessian of the log-likelihodd. For both methods, the priors 2 0 and H g.o La were used, and sequential updates were performed every iteration. The sample criterion for BALD under logistic model is given in Appendix B.5.1. For BayesGURO, 50 posterior samples were used to estimate Vo pr [a<0" zzy)] for every Zuy. The hybrid algorithms follow same structure with the added constraint that each per-item parameter Ç is independent of other parameters. This allows for efficient updates of H Hg. by using sparsity in the covariance.
GURO, CoLSTIM, and Uniform use LogisticRegression from Scikit-Icarn (Pedregosa et al., 2011) with default Ridge regularization (C' = 1) and the Ibfgs optimizer. The former two updates O, every iteration using the full history, D, in all experiments except for IMDB-WIKI-SbS. where GURO updates 0, every 25th iteration. This caused no noticeable change in performance as GURO still updates H," every iteration using the Sherman- Morrison formula. Note that when using the Sherman-Morrison formula in practice, you only get an estimate of H, (6.) since previous versions have been calculated using older estimates of 0. This method for approxi- mating the inverse hessian is covered in Bishop and Nasrabadi (2006, Chapter 5) and when compared to calculating (0,) from scratch every iteration
observed that the methods performed equally. The design matrix for CoLSTIM is updated as in Bengs al. (2022): the confidence width was chosen to be / log'", and the perturbed values were generated using the standard Gumbel distribution.
To increase computational efficiency for the large IMDB-WIKI-ShS dataset, the hybrid algorithms did not evaluate all ~ 100 000 comparisons at every time step. Instead, a subset of 5 000 comparisons was first sampled, and the highest-scoring pair in this set was chosen, This resulted in large speed-up and no noticeable change in performance during evaluation.
E.1 Datasets
ImageClarity Data available at httpe://dbgrout wtt..c..aaaaa... tti..nhuaaa.... edu. cn/Lig./croodttpk. This dataset contained differently distorted versions of the same image. To extract relevant features, we used a ResNet34 model (He et al., 2016) that had been pre-trained on Imagenet (Deng et al., 2009). After PCA projection feature dimensionality was reduced to d = 63. The dataset consisted of 100 images and 27 730 comparisons. Since the type of distortion the same for all images, the dataset has a true ordering with regards to the strength of the distortion applicd.
Ads Data available :0i:10. 7910/DVM//ZRGGEZ (license: CCO 1.0). The WiscAdds dataset, containing 935 political texts, has been extended with 9 528 pairwise comparisons by Carlson and Montgomery (2017). In comparisons, an- notators have stated which of two texts has more negative tone toward political opponent. To extract general features from the text, sentences were embedded using the pre-trained all-mpnet-base-ve model from the Transfoorrrrssssse library (Reimers and Gurevych, 2019). After applying PCA to the sentence embed- dings, each embedding had dimensionality of d = 162.
haaraaaaaaaeereeeaaaaa.d.d. harvard. edu/ dwtasat.ateeeeeeeeeee www.:x/lmmmmxiieeeem Ptttmm/pprriittttIdd
Data available at IMDB WIKI-SbS consists of closc-up images of actors of different ages. For each comparison, the label corresponds to which of two people appears older. The complete dataset consists of 9 150 images and 250 249 comparisons, but images that were grayscale or had resolution lower than 160 160 were removed, resulting 072 images and 110 349 comparisons. We extract features from each image using the Inception-ResNCe implemented in FaceNet (Schroff et al.. 2015) followed by PCA, resulting in d 75 features per image.
IMDB-WIKI-S WIKI-SBS
com/Toloka/IMD: -IIIa//IIDD-IIIII---- WIKI-StS (license: CC BY).
E.2 Additional figures
X-RayAge
To highlight the importance of the first-order term in Lemma we evaluated NormMin on the same X-ray ordering task as Figure la. The results, shown in Figure 3a, indicate that not only does the algorithm perform worse than GURO, but is seemingly also outperformed by a uniform sampling strategy. Furthermore, for com- pleteness, we include Figure 3b which shows the in-sample error, RI during the generalization experiment.
Synthetic Example and Illustration of Upper Bound
In this setting, 100 synthetic data points were generated. Each data point consisted of 10 features, where the feature values were sampled according to standard normal distribution. The true model, A., was generated by sampling each value uniformly between -3 and 3. The pairwise comparison feedback was simulated the same
27

---

0.200
0.200
Unifumm
Uniform
0.175
Norm Kontdalls Tau distanoe
0.175
GURD
BayesEURO
0.150
BALID
COLSTIM
0.125
0.125
0.075
0.075
0.050
0.050
0.025
0.025
0.000
0.000
1000 1250 1500 1750
2000
500
750
1000 1250 1500 1750
Comparisons
Comparisons
(a) X-RayAge. NormMin included the experiment shown in Figure la.
(b) X-RayAge- The in sample error Rio for the gen- eralization experiment performed in Figure lb.
Figure Additional figures from the X-RayAge experiment.
way in Section 6.1, with À 0.5. The upper bound of the probability that R(0:) 2 0.2 calculated every iteration according Theorem Each algorithm was run 2000 comparisons, updating every 10th, the results of which can be seen in Figure 4. We observe in Figure 4b that our greedy algorithms are seemingly the fastest at minimizing the upper bound. The order of performance follows the same trend as in the experiments of Section 6.
0.30
Uniform
Uniform
0.25
BayesGURO
GURO
0.8
GURO
BayesCURO
BALD
PoRid
BALD
0.20
STL
0.6
CoL.TTIM
NormMin
NormMin
0.4
0.05
0.00
250
500
750
1000
1250 1500
1750 2000
250
1000 1250 1500
2000
Comparisons
Comparisons
(a) The risk R(O.). defined as the normalized Kendall's tau distance between estimated and true or- derings.
(b) The probability that frequency pairwise versions is 2 20% after every comparison, according to (1).
Figure 4: The loss (left) along with the upper bound (right) when ordering a list of size 100 in synthetic environment. The results have been averaged over 50 seeds.
Randomly initialized representation
As discussed in Section 6.2, the performance of our contextual approach will depend on the quality of the rep- resentations. To underscore the practical usefulness of our algorithms, we have performed the same experiment in Figure 2c, but this time the madel used extract image features was untrained (i.e., the weights were random). As be expected, the results, shown Figure 5, demonstrate that the fully contextual algorithms have no real way of ordering the items according to these uninformative features. However, GURO Hybrid performs similarly to TrueSkill, despite model misspecification. This is promising, since you may not know in advance how informative the extracted features will be for the target ordering task.
28

---

Error on holdout comm comparison
0.45
0.40
Unilorm Hybrid
GURO
0.35
BALD
0.30
Hybrid
True Skill
0.25
0.20
0.15
0.10
10000
40000
50000
Comparisons
Figure 5: IMDB-WIKI-SDE The same experiment as presented in Figure. 2c, but the model used for feature extraction is untrained.
ImageClarity ground truth
The ImageClarity dataset consists of multiple versions of the same image, with the same distortion applied to to varying degrees. Due to this artificial construction, the pairwise comparisons should, given enough samples, reflect the magnitudes of the applied distortions. In Figure 6 we perform the same experiment in Figure 2a, but instead of evaluating The overall results are very similar, although we do see slight increase in the performance of contextual algorithms compared to the non-contextual TrueSkill.
holdout comparison set, we measure the distance to the ground truth ordering.
0.5
Unitorm
Norm. Kendall's Tau distance
Uniform I[ybrid
0.4
GURO
GURO 1lybrid
BALD
Hybrid
0.3
TrueSkil
0.2
0.1
0.0
100
200
300
400
500
600
700
800
Comparisons
Figure 6: ImageClarity. Same experiment as in Figure 2a, but now measuring the distance to the ground-truth ordering. Averaged over 25 seeds along with the I-sigma error region.
Ground truth ordering using the Bradley-Terry model
An alternate approach evaluate ordering quality estimate "ground-truth" ordering by applying the pop- ular Bradley-Terry (BT) model (Bradley and Terry, 1952) to available comparisons. We used the CrowdKit library (Ustalov et al., 2024) to find the MLE scores for each item and ordered the elements accordingly. In Figure 7 we run the same experiments in Figure 2. but instead measure the distance to the constructed BT ordering. The overall trends remain, but for (b) and there is slight shift for the later iterations. More specifically we see non-contextual TrueSkill eventually overtaking the contextual algorithms.
The issue is that algorithms with orderings closer the maximum likelihood estimate of the BT model will be favored. To exemplify this we use the IlagoClarity dataset since it contains the largest number of comparisons relative to the number of items. We sample 000 comparisons and let this be the collection that is available to the algorithms. We further construct two target orderings. one from the BT estimate using the sampled subset of comparisons, and second, parisons. Figure shows the distance between GURO and algorithms and different target orderings, where dashed lines indicate the distance to the ordering generated using the full list comparisons. we only look at the distance to the ordering produced using our subset of comparisons, TrueSkill seemingly outperforms GURO after about 350 comparisons. However, if instead measure the distance the probable order-
probable ordering, from the BT estimate using all 27 730 available
29

---

Uniform
GURO
BALD
TrueSkill
Uniform Hybrid
GURO Hybrid
BALD Hybrid
0.5
0.5
0.100
Norm. Kondall's distance
Norm. Kendall's Tau disiance
0.1
0.125
0.050
0.100
0.3-
0.026
650
700
750
0.050
4250
4500
4750
0.2-
0.2
0.1
0.1
0.0
100
200
300
100
500
600
700
800
1000
2000
3000
4000
5000
Comparisons
Compansons
(a) ImageClarity, = 100, d = 63.
(b) WiscAds. n 935, = 162.
0.5
0.125
Norm. Kendall's Tau distancn
0.4
0.100
0,075
0.3
0,050
47500
0.2
0.1
0.0
10000
20000
30000
40000
Comparisons
(c) HMDB-WIKI-Sh.. 6 072, d 75.
Figure 7: The same experiment as presented Figure. 2c, but we instead measure the distance to a ground-truth estimated using all available comparisons.
ing, we see that GURO converges toward lower distance. Note that these are the same orderings, evaluated against different targets. This is likely the effect observe in Figure 7b and but not in Figure 7a as result of the high amount of comparisons available
GURO
Norm. Kendall's Tau distance
GURO Full
Tril
TrueSkill Full
0.3
0.2
0.1
0.0
100
200
300
400
500
600
700
800
Comparisons
Figure 8: ImageClarity. The same experiment as presented Figure 2a, but we instead measure the distance to target orderings that correspond to the maximum likelihood estimate of the BT model using different numbers of comparisons. The dashed lines show the distance to the BT estimate using all 27 730 comparisons.
30

---

NeurIPS Paper Checklist
1. Claims
Question: the main claims made abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the introduction, we clearly state where in the paper each contribution can be found.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made in the paper and important assumptions and limitations. A No NA question will not be perceived well by the reviewers.
this
The claims made should match theoretical and experimental results, and reflect how much the results can he expected to generalize to other settings.
fine to include aspirational goals as motivation long clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In Section 7 we highlight limitations such as real data experiments not being performed in online setting and the lack of optimality guarantees for algorithm.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper limitations, but those are not discussed in the paper.
The authors are encouraged create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results tions 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.
viola-
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested a few datasets with few runs. In general, empirical results often depend implicit assumptions, which should he articulated.
The authors should reflect 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 a speech-to to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
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 prob- lems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important 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 of assumptions and plete (and correct) proof?
Answer: [Yes]
Justification: We clearly define our problem setting in Section 2, including relevant assumptions. Additionally, in Section 4 we list the three assumptions that our analysis depends on, and include the complete proofs in Appendix C.
Guidelines:
The answer NA means that the paper does not include theoretical results.
31

---

All the theorems, formulas, and proof' in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental matcrial, the authors encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by
formal proofs provided in appendix or 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 experimen- tal results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Among our main contributions are the GURO and BayesGURO sampling strategies, which we not only offer al algorithmic descriptions of but also provide the code for. We also descrihe our experimental setup in Section 6 and Appendix E including hyperparameters and pre-trained models used for feature extraction.
Guidelines:
The answer NA means that the paper does not include experiments.
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 not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For ex- ample, if the contribution novel architecture, describing the architecture fully might suffice, the contribution is specific model 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 replicate the results, access to a hosted model (e.g., the case of a large language model), releasing checkpoint, or other means that are appropriate to the research performed.
model
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g.. 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 some cases, which case authors are welcome to 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 (e.g., registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We provide code in publicly available repository. We have also provided links from which the datasets can downloaded.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines htttps://nips.cc/eee quiddes//odeSttbmissiooooo...... for more details.
32

---

While we encourage the release of code and data, understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this central to contribution (e-g.. for a new open-source benchmark).
The instructions should contain the exact command and environment needed duce results. See the NeurIPS code and data submission guidelines (https: http://iiisccceee cc/ public/guse Seniidde/CooSSumiisssstssss
repro-
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 a subset of experiments are reproducible, they should state which ones 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 to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide experimental details, including splits and hyperparameters, in Section 6.2 as well as Appendix E.
Guidelines:
The answer NA mcans that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can he 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 infor- mation about the statistical significance of the experiments?
Answer: [Yes]
Justification: In Section 6 we either provide 1-sigma error bars the 95% confidence interval, ex- plicitly stating which in the figure captions.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence inter- vals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors variability that the emrrr bars are capturing should 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).
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 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of emrors is verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are of range (c.g. negative error rates). If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on computer re- sources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
33

---

Justification:
In Section 6.2 we state the compute resources used for the most demanding experiments.
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, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimen- tal runs as well as 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 failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics battps://neur/e httpp/pp/pppppbcc//cteeei...aaaa
Answer: [Ys]]
Justification:
We have read and ensured that our work conforms to ethical guidelines stipulated.
Guidelines:
The answer means that authors have not reviewed NeurIPS Code of Ethics. the authors answer No, they should explain the special circumstances that require deviation from Code Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal im- pacts of the work performed?
Answer: [Yes]
Justification: In the introduction, we descrihe our motivating example of annotating medical images. Enabling quantitative analysis of these images could be highly beneficial for medical research. We do however not direct path from active sampling criterion negative application.
Guidelines:
The answer NA means that there is societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (c.g., dis- information, generating fake profiles, surveillance), faimess considcrations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy consid- erations, and security considerations.
The conference expects that many papers will be foundational research and not tied to par- ticular applications, let alone deployments. However, there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used generate deepfakes for disinformation.
other hand, it is not needed to point out that generic algorithm 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 is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative socictal impacts, the authors could also discuss possible mitigation strate- gies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, im- proving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g.. pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: The algorithms provide do not pose any particular risk for misuse.
34

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be relcased with necessary safeguards to allow 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
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 cite the authors of all datascts we use according to their wishes in Section 6. We fur- ther include URL's 's in Appendix E.1 along with licenses for all available datasets except ImageClarity, for which we could not find the relevant information.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from 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, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pacaaeed, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's creators.
13. New Assets
Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
We do not introduce any new assets.
Guidelines:
The answer NA means that the paper does not release
Researchers should communicate the details of the dataset/code/moodll part of their submis- sions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL include an anonymized zip file.
14. 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, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: We have not performed any crowdsourcing experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
35

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to subjects, and whether Institutional Review Board (IRB) approvals (or an equiv- alent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: We did not perform any experiments 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 the paper.
We recognize that the procedures for this may vary significantly between institutions and lo- cations, and we expect authors to adhere the NeurIPS Code of Ethies and the guidelines for their institution.
include any information that would break anonymity (if applica- ble), such as institution conducting the review.
initial submissions,
36


Reviews:
[{"review_id": "FVEzBYXHNT", "reviewer": "Reviewer_LY2M", "summary": "This paper considers the setting of learning an ordering between items according to some scoring rule. The assumption is that this ordering is determined by a contextual scoring rule, determined from the features of each item. Such contextual structure can aid in more rapidly learning an ordering, and generalizing to out of sample items. This ordering is learned from asking pairwise preferences to an oracle, reducing uncertainty about the total order. Since there are a large number of possible comparisons to be asked, active learning is deployed to only query labels for a subset of comparisons. A theoretical argument is made about the optimal balance between aleatoric and epistemic uncertainty to target in adaptive selecting queries, motivating the GURO adaptive sampling strategy and variants. The performance of GURO is demonstrated in several empirical experiments on simulated data and data collected (offline) from real humans.", "questions": "- I think the statement \"Moreover, the set we want to order is often larger than the set of items observed during training—we may want to rank new X-rays in relation to previous ones. This cannot be solved using per-item scores alone.\" should be clarified. If one knew absolute scores for all items (regardless if they are observed in training), isn't it trivial to compute an ordering? Or did the authors mean that pairwise responses collected during training could not generalize outside of training, without example features to predict from? [Edit: this does seem to be clarified in Section 2, but should be made more clear in the introduction]\n- I find the sentence \"However, as we show in Section 4, learning this map to recover a complete ordering is distinct from the general preference learning setting, and existing algorithms lack theoretical justification for this application\" to be vague and should be clarified. What exactly is the \"general preference learning setting\", versus learning a map to recover complete orderings? What does \"this application\" refer to? Which of these two settings are you concerned with here?\n- I'm confused by line 159. Why can one lower bound $\\Delta_{ij}$ by a factor depending on the index difference $\\lvert i -j \\rvert$? Aren't the indices arbitrary, and agnostic to the underlying geometry of the feature space? Does this mean that a simple index permutation would drastically change this $\\Delta$ quantity?\n- in line 166, should the dependence not be on $\\theta_T$ rather than $\\theta_*$?. See line 157 which uses $\\theta_T$. line 169 also jumps back to $\\theta_T$\n- line 189 is missing an important point: by definition the entirety of $\\mathcal{I}$ is unavailable, only $\\mathcal{I}_D$ is available to select from. This should be commented on.\n- I think line 198 is too vague: \"As θt converges to θ∗, this pair becomes representative of the maximizer of (4) provided there is no major systematic discrepancy between ID and I.\" Can you comment more on what constitutes acceptable vs unacceptable discrepancies between I and I_D? This does bring up a problematic point: what if $I_D$ is not sufficiently representative of $I$? Line 215 starts to hint at this discussion but I think it needs to be elaborated on, ideally more formally\n- in GURO Hybrid, how are these $\\zeta_i$ parameters actually learned? Is it just a joint MLE on $\\theta$ and $\\zeta_i$? In this case, what prevents the model from learning an arbitrary $\\theta$ (i.e., $\\theta = 0$) and just using the full expressivity of $\\zeta_i$? Is there some sort of regularization in practice?\n- for completeness, can you include a figure in the Appendix showing the experiment in Fig 1b, but just plotting $R_{I_D}$ instead of the difference? It would be good to know how each algorithm does in an absolute sense on $I_D$\n- figure 2 would benefit from a log y scale - it is very difficult to discern between methods\n\nMinor:\n- line 147 uses the notation $\\widehat{H}$ instead of $\\widetilde{H}$. I assume this is a typo\n- missing left parentheses in line 5 of GURO algorithm\n- the word BayesGURO in Algorithm 1 should also probably be colored green to show the association to (7) and (11)\n- be careful with red and green as distinguishing colors for readers with color vision deficiency\n- fix quotes on line 258", "limitations": "Yes", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I believe this paper is excellent - it is *clearly* written, has a great flow, and theoretical and empirical arguments are tied together nicely to motivate the problem setting, establish the problem fundamentals, convey mathematical intuition about uncertainty reduction, and justify active selection. There is also a robust set of experiments demonstrating GURO (and variants) in practice against baselines, along with explanatory discussion and implementation details. To my knowledge the analysis and algorithmic ideas here are *original*, and this is a *high quality* submission. Although not the centerpiece of this work, in an age where RLHF and efficiently learning from human preferences is paramount in training large models and ranking queries, work in active preference learning and the contributions made here are *significant*. There is also a robust and thorough appendix providing details and theoretical proofs (disclaimer: I have read the main paper in careful detail, but only skimmed the appendix). Overall, this is elegant, interesting, and impactful work (both theoretically and empirically).", "weaknesses": "I do not have any explicit weaknesses to list. Instead, I have a list of comments and questions below that I would like the authors to address. However I feel confident that these can be addressed during the rebuttal phase.\n\nOne comment is that there is no discussion (unless I missed it) about computational complexity stating and comparing the big-O computational complexity of GURO, its variants, and other selection methods. This would be an interesting and strengthening addition to this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**R: The definition of \"general preference learning'' and its distinction from the current setting**\n\nWe agree that this can be clarified further. This paper focuses on learning a map to recover a complete ordering, but we leverage active preference learning to achieve this.  By ''the general preference learning setting'' we refer to existing literature that adaptively samples pairwise comparisons, subsequently observing which of two items is preferred, to learn a comparison function $h(i, j)$. Much of this related work focuses on learning a parameter vector ($\\theta$) [1,2,3]. Our approach is a special case of this, and while we are trying to learn $\\theta$, we are only doing so as far as it helps us order our list of items. Existing work emphasizes getting good approximations of $\\theta$, with [1] maximizing $\\hat{\\theta}^T \\theta$, while [2,3] try to minimize $|\\hat{\\theta} - \\theta|_2$. If the true vector $\\theta$ is known, it is sufficient to order the list. However, reducing uncertainty in all directions will likely be wasteful; we do not care about the accuracy of $\\theta$ in directions that do not help determine the ordering. As highlighted in Figures 1a and 2c in our paper, while BALD is constructed to efficiently learn parameters by sampling pairwise comparisons, it is ill-suited for full rank recovery.\n\n**R: In GURO Hybrid, how are these parameters actually learned? Is there some sort of regularization in practice?**\n\nYes, the parameters are learned through joint MLE on $\\theta$ and $\\zeta_i$, with regularization, as you suggest. The regularization prohibits the algorithm from learning an arbitrary $\\theta$. We cover experimental details, including regularization, in Appendix F. However, we agree that this information is essential for the hybrid model and will include this motivation in the main paper for the final version.\n\n**R: Line 198 is too vague: Can you comment more on what constitutes acceptable vs unacceptable discrepancies between $\\mathcal{I}$ and $\\mathcal{I_D}$?**\n\nTo learn the ordering perfectly, the feature differences for pairs of items in $\\mathcal{I_D}$ must span the space spanned by the feature differences for pairs in $\\mathcal{I}$. This is true with high probability when $\\mathcal{I_D}$ is a random subset of $\\mathcal{I}$, the dimension $d$ is small relative to $|\\mathcal{I_D}|$ and the variation in directions of $z_{ij}$ for $i,j \\in \\mathcal{I}$ is sufficient (i.e., each direction is sufficiently covered). An ``unacceptable'' case would be where one dimension of $z_{ij}$ has large variance for some pairs $i,j \\in \\mathcal{I}$ but is constant for pairs in $\\mathcal{I_D}$. In this case, the component of $\\theta$ in this dimension would not be learned consistently, and the model would generalize poorly to $\\mathcal{I}$.\n\n**R: Clarification regarding sorting \"using per-item scores alone\" in the introduction**\n\nThe assumption here is that you don't have any contextual features available (or that your sorting algorithm does not utilize them) and that per-item scores are not known from the beginning but have to be estimated by observing pairwise comparisons. In this scenario, when new items are added to the collection we have no way of estimating their underlying scores (apart from arbitrary initial values such as the average) before observing further comparisons where they are included. This is exemplified by TrueSkills performance in Figure 2d.\n\n**R: Line 159: Why can one lower bound $\\Delta_{ij}$ by a factor depending on the index difference $|i-j|$?**\n\nThis follows from the definition of $\\Delta_* = \\min_{i\\neq j} \\Delta_{ij} /(i-j)$. The indecies are actually not arbitrary but we assume, w.l.o.g, that the items are ordered such that $i > j$ implies $y_i > y_j$. This was stated in the appendix and we will move it to the main paper. The idea is that we can now lower bound $\\Delta_{ij}$ by a constant, $\\Delta_*$, times how close the two items are to each other in the ordered list, $|i-j|$. This allow us to simplify the lower bound stated on line 158 since each element in the sum now depends on $\\Delta_* |i-j|$ and we can treat it as a geometric sum. \n\n**R: Discussion on the computational complexity of GURO and its variants**\n\nThank you for suggesting this addition. We include a discussion on this topic in the general rebuttal since two reviewers raised the issue. We intend to add this discussion to the final version of the paper.\n\n**R: For completeness, can you include a figure in the Appendix showing the experiment in Fig 1b, but just plotting $R_{I_D}$ instead of the difference?**\n\nWe agree with the reviewer that this would be good for completeness and will include this figure in the appendix for the final version. We have attached the produced figure to the general rebuttal.\n\n**R: in line 166, should the dependence not be on $\\theta_T$ rather than $\\theta_*$? See line 157 which uses $\\theta_T$. line 169 also jumps back to $\\theta_T$**\n\nYes it should be $\\theta_T$, thank you for pointing this out.\n\n**R: line 189 is missing an important point: by definition, the entirety of $\\mathcal{I}$ is unavailable, only $\\mathcal{I_D}$ is available to select from. This should be commented on.**\n\nYes, this is correct, direct minimization of (4) would be impossible considering we only have access to a subset $\\mathcal{I_D}$. We will note this in the final version of the paper.\n\nWe thank LY2M for the thorough feedback and for believing that our contributions are of great value. The remaining comments (including minor ones) have been addressed in the updated manuscript. \n\n**References**\n\n* [1] Qian, et al. (2015). Learning user preferences by adaptive pairwise comparison. Proceedings of the VLDB Endowment.\n\n* [2] Canal, et al., (2019). Active embedding search via noisy paired comparisons. International Conference on Machine Learning.\n\n* [3] Massimino, and Davenport (2021). As you like it: Localization via paired comparisons. Journal of Machine Learning Research.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "soeZBnWo5J", "reviewer": "Reviewer_nNXZ", "summary": "Active preference learning is different from deriving a complete ordering from preferences. It focuses on “If we collect comparisons D_T, how good is the resulting model’s predicted ordering in the item set”.  The paper proposes a sampling method in the active learning scenario. Theoretical analysis is also provided.", "questions": "State-of-the-art baselines should be added for performance comparison.", "limitations": "Limitation should be added.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "--Preference learning is critical to many downstream tasks.\n\n--The proposed method is somewhat novel.\n\n--The theoretical analysis is provided.\n\n--Experimental results are shown to verify its effectiveness.", "weaknesses": "--The assumption 1 and 2 are not so intuitive. It is better to illustrate an example.\n\n--Baseline methods are weak. Though many related studies are mentioned in the related work section, performances of baselines are not shown in the experiments.\n\n--The number of comparisons is  not reduced tremendously on the ImageClarity in Table1.\n\n--Performances should be emphasized in terms of the prediction ordering quality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**R: Baseline methods are weak. Though many related studies are mentioned in the related work section, performances of baselines are not shown in the experiments.**\n\n* We argue that the baselines we have included are state-of-the-art and come from diverse fields: Active Preference Learning, Logistic Bandits, Non-Contextual Sorting. \nSince there is limited work on recovering a complete ordering using contextual attributes, there are no well-established benchmarks to beat. \n\n* We have selected baselines to study three main questions: the effects of including contextual information, the impact of the sampling criterion and the difference between in-sample and out-of-sample ordering.  Most algorithms discussed in the related work section are **related** but are **not** designed to solve our problem, and would not give evidence for these questions. \n\n* Many algorithms would either perform poorly or do not work in the offline setting where we are limited to a subset of comparisons. [1] does not work on a subset of comparisons and assumes no noise. [2] account for noise by collecting $N$ annotations for *every* comparison pair, which is not resourceful and is not possible in most practical settings, including the tasks in our empirical study. Several methods in the related work section do not use contextual information, and TrueSkill (which is included in our study) is considered the state-of-the-art for this group. We welcome specific suggestions for stronger baselines to include.\n\n**R: Performances should be emphasized in terms of the prediction ordering quality.**\n\nWe agree that obtaining a good ordering is the focus of this paper, but a ground-truth ordering does not exist for most datasets where comparisons have been made by human annotators since individual annotators often disagree and no annotator labels all pairs. In Figure 7 in Appendix F.2, we perform the same experiments as in Figure 2, but we instead measure the ordering error compared to an ordering estimated from all available comparisons. While this offers similar results, we discuss why this approach can be problematic and highlight this with an example below. In the case of ImageClarity, where the true ordering was available, we evaluate against this in Figure 6 in Appendix F.2. as well, and show that the results mirror our findings in Figure 2.\n\n**R: The assumption 1 and 2 are not so intuitive. It is better to illustrate an example.**\n\nWe thank reviewer nNXZ for this suggestion and will include the motivation behind these assumptions in the updated manuscript.\n\n* Assumption 1 implies that the $\\theta_*$ lies in some bounded ball and cannot have unbounded coefficients. We use this assumption on line 705 and we believe this assumption to be necessary since it wouldn't be possible to bound the maximum distance between some unknown $\\theta'$ and the true $\\theta_*$ otherwise. Note that this assumption is not limiting since the bound on $\\theta_*$ is not used by our algorithms. \n\n* Assumption 2 states that there exists an upper bound on the norm of the feature vectors. This assumption is trivially satisfied whenever we have a finite set of data points.\n\nBoth assumptions are standard in the literature and only required for the analysis. \n\n**R: The number of comparisons is not reduced tremendously on the ImageClarity in Table1.**\n\nThis is true. We state in Section 6.2 that this is most likely a result of it being easy to order the images in ImageClarity based on their extracted features due to the low semantic level of image distortion. We still include this experiment to highlight that:\n\n* Hybrid models are sometimes not necessary.\n\n* There is still a clear difference between the contextual and non-contextual algorithms.\n\n* Uniform performs worse than active sampling criteria.\n\nWe cannot expect any method to beat all other methods on every task, and we are happy to show examples where several methods work well.\n\n**R: Limitation should be added.**\n\nIs there a specific limitation you are referring to? In Section 7 we cover limitations, such as the lack of a lower bound, and future directions, such as applying representation learning and performing experiments in an online setting. We are happy to include other limitations in an expanded discussion for the final version. \n\n**References**\n\n* [1] Nir Ailon. Active learning ranking from pairwise preferences with almost optimal query complexity\" Advances in Neural Information Processing Systems, 2011\n\n* [2] Kevin G Jamieson and Robert Nowak. \"Active ranking using pairwise comparisons\" Advances in neural information processing systems, 2011", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IsUhJTg7hU", "reviewer": "Reviewer_6ajg", "summary": "This paper considers the ranking problem based on pairwise comparisons. The goal is to get the best sampling strategy for the best ordering from a limited number of comparisons. Under a logistic model on the difference between scores, the authors provide the analysis for the upper bound on the ordering error, which provides insights on sample selections. Following the idea of minimizing the bound, this paper proposes the GURO algorithm for pair selections. The proposed method is evaluated in four image ordering tasks with either synthetic labels or real world labels.", "questions": "Please provide more discussion on how difference the proposed method is comparing to logistic bandits.", "limitations": "Yes, the authors touch upon the limitation in the conclusion section.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The proposed algorithm is well motivated by the theoretical result on the ordering error. It has very strong theoretical guarantees on the performance. The theory presented in the paper looks good to me. And it helps the reader to understand the algorithm better with some justification from Bayesian analysis. \nI find the paper very well written. The way the authors presented the results is very clear and easy to follow.", "weaknesses": "Although the theory presented in the paper looks good to me, I find it very similar to the result presented in the original Logistic bandit paper [1]. By treating the input space as the difference between features, the problem is simplified to a standard logistic bandit problem. And The result in Lemma 1 and some analysis before Theorem 1 are very similar to Lemma 2 and 3 in [1]. While I understand Theorem 1 is specifically for the ranking error, I think it is still straightforward to get Theorem 1 from existing lemmas.\nAnd for the empirical study, I see the proposed approach actually does not always perform better than baselines, especially BALD. The good result is on synthetic data, there is no significant advance on real data. Therefore, I am not convinced with the claimed statement in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**R: Please provide more discussion on how difference the proposed method is comparing to logistic bandits.**\n\nAs mentioned in our submission (l109, l138), our theory builds on the same techniques as previous papers on logistic bandits. However, we want to highlight that the problem considered here differs substantially from the standard bandit problem. Lemma 1 is a standard argument used in the literature (even before logistic bandits) which we include and tailor to our setting for completeness. Moreover, Theorem 1 is tailored toward our setting and justifies a selection criterion that is good for ranking but not for (regret minimization) bandits.\n\nReviewer 6ajg did not specify which paper \"[1]\" is referring to but if it is Faury et al. (2020), the reviewer is correct that Lemma 1 is similar to their Lemma 3. An important distinction is that we provide a bound on the probability of error while they offer a high-probability upper bound on the prediction error. In principle, one can turn a bound on the prediction error to a bound on the probability of error. However, in the case of Lemma 3 in Faury et al. (2020), this would require solving a difficult expression involving squares of logarithmic terms. We are not sure this can be done in an analytical way that results in a parsable final bound. The reason that we can present a clean upper bound is due to the decomposition on l687 where we decompose the prediction error into first and second-order terms and then proceed to bound them independently. This is a new contribution in our work. \n\n**R: The proposed approach actually does not always perform better than baselines, especially BALD. [...] Therefore, I am not convinced with the claimed statement in the paper.**\n\nWe assume that the reviewer is referring to the claim of superior sample efficiency. This claim refers to a comparison with previously published algorithms (Uniform, BALD, CoLSTIM, TrueSkill). In all cases in Figures 1-2, a method proposed in this work (GURO, GURO Hybrid or BALD Hybrid) performs better than these baselines, although the difference on ImageClarity is smaller. For the fully contextual versions, GURO consistently uses fewer samples than BALD to reach the same ordering quality, thus having superior sample efficiency. GURO Hybrid and BALD Hybrid are close but GURO Hybrid is never worse. Both are consistently better than TrueSkill. These are new results that were not known in previous research. \n\nIn Section 6.2 we reason that the cause of the similar performance between BALD Hybrid and GURO Hybrid is the increased dimensionality due to item-specific terms leading to BALD attributing more of the errors to epistemic uncertainty. It is possible that we would eventually see a similar plateau for BALD Hybrid in 2b as in 2c, but due to us having a limited amount of pre-collected annotations, these experiments can't be extended much further without the overlap of comparisons selected by the algorithms becoming too large. We emphasize that the Hybrid model is a novel contribution presented in this work. It is a pragmatic solution to utilize contextual attributes even when they are not sufficient to produce a complete ordering.\n\nWe agree that our claims regarding the empirical results can be clarified further in the abstract and the introduction, and will therefore take steps to:\n\n* Clarify what we mean by GURO having superior performance to active preference learning baselines. \n\n* Further highlight that BALD Hybrid is new to this work. \n\nFinally, beyond GURO and Hybrid variants, we believe that one of this paper's main contributions is the evaluation of existing algorithms when applied to recover a complete ordering. To the best of our knowledge, this is the first time BALD has been used explicitly to order a list. Our experiments, where we also apply our hybrid modification, offer insights into when this works well (BALD in Figure 2a, BALD Hybrid in 2b), and when this does not (BALD in all Figures except 2a, BALD Hybrid in 2c).\n\nWe thank reviewer 6ajg for their critique and will use this input to clarify our claims and contributions for the final version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AlzbY63fbA", "reviewer": "Reviewer_tuDy", "summary": "This paper proposes an active learning algorithm for selecting pairs of items for comparison in order to learn a ranking of the items.\nThe ranking error is measured by the (normalized) number of swapped pairs compared to the true ordering (Kendall’s Tau distance). The algorithm chooses pairs of items based on an upper bound on this ranking error. Experiments are conducted on one synthetic and 3 real-world benchmarks.", "questions": "* “We restrict algorithms to only query pairs for which an annotation exists and remove the pair from the pool once queried.” – What is the number of available annotations for each dataset in figure 2 in the experiments? Only the number of items n and the dimension d are specified. Also, there is no notion of annotation noise here, since the labels are set, right?\n\n* What is $\\Delta_*$? It seems from line 159 that: $\\Delta_*=\\min_{i,j} \\Delta_{ij}/|i-j|$, but it would be better to define it explicitly. Does it really depend on the index difference $|i-j|$? What is the reasoning behind this?\n\nMinor:\n* Line 74: “Ordering algorithms based only on preference feedback cannot solve this problem since observed comparisons are uninformative of new items.” This statement is not clear, as long as items are represented as attributes/features $x_i$ then comparisons may be informative for new items.", "limitations": "I suggest adding the assumption on response (eq 2) and the $O(n^2)$ complexity to the list of limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* Active learning for pairwise comparisons is an interesting problem to study\n* The approach is justified by theoretical analysis\n* The empirical evaluation looks promising", "weaknesses": "* The paper uses strong assumptions on the pairwise comparisons. Specifically, the response is assumed to be: $P(C_{ij}=1) = \\sigma(\\theta_*\\cdot(x_i-x_j))$, where $\\sigma$ is the sigmoid function (eq 2). These assumptions are used for fitting MLE parameters. These assumptions are common in the literature.\n\n* The optimization problem for choosing a pair (eq 5 and 7) seems hard. The cost is quadratic in the number of items since all pairs are considered. An approximation that depends linearly on the number of items would make the approach more practical.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**R: The response is assumed to be: $P(C_{ij}=1) = \\sigma(\\theta_*(x_i-x_j))$.**\n\nWhile this assumption underlies our theoretical analysis and motivates the current version of GURO, we believe that we have taken many steps to highlight the practical usefulness of our algorithm and that the results are more generally applicable.\n\n* We describe in Appendix D.3 how one can derive similar results for other generalized linear models, meaning that one can extend these results beyond the logistic feedback setting.\n\n* We introduce a hybrid model that is aimed at overcoming model misspecification. In Figure 5 in Appendix F.2 we show that these hybrid models still perform comparably to non-contextual algorithms even when features are completely uninformative.\n\n* In Figure 2, we evaluate comparisons made by human annotators. While the algorithm uses a logistic model, the data does not adhere to this. Still, we observe good convergence properties. GURO outperforms TrueSkill, an algorithm that does not assume a logistic model. \n\nFinally, we thank reviewer tuDy for noting that these are common assumptions. \n\n**R: The optimization problem for choosing a pair (eq 5 and 7) seems hard.**\n\nThe motivating example for this paper is the annotation of medical images. As annotations made by radiologists are expensive, our main goal has been to minimize sample complexity, or as stated in the introduction: ''... how can we learn the best ordering possible from a limited number of comparisons?''. We believe that the algorithm is already practically applicable as the bottleneck will in most cases be the time it takes the user to perform a comparison (e.g., about 6 seconds in the case of IMDB-WIKI-SbS). It is however true that for large collections, computational bottlenecks can be encountered if we evaluate all possible comparisons at every iteration, a problem shared by most active preference learning algorithms [1,2,3]. As we describe in Appendix F, in the cases where $n^2$ is large we can instead evaluate our sampling criterion on a uniform subsample of candidate comparisons with no noticeable impact on performance, similar to [2].\n\nSince the computational complexity of GURO was of interest to reviewer LY2M as well, we have written a discussion regarding this in the general rebuttal which we intend to include in a final version. This discussion also includes a potential alternative version of the sampling criterion that scales linearly with $n$.\n\n**R: There is no notion of annotation noise here, since the labels are set, right?**\n\n The label for each **annotation** is set, but there is still noise in the **comparisons**. This is perhaps most clear for the ImageClarity dataset where each comparison has been annotated more than 5 times on average by different annotators. As these annotators can disagree with each other, we get different comparison outcomes depending on which annotation we sample. Furthermore, even in the case where we don't have multiple annotations for each comparison, we still observe noise since annotations can be inconsistent. Say the true order is $a \\succ b \\succ c$. We might observe the three annotations: $a \\succ b$, $b \\succ c$, and $c \\succ a$. The final annotation is inconsistent with the best possible ordering, but we likely observe this in our data as human annotators disagree with each other and do not necessarily provide responses consistent with their previous comparisons. These inconsistencies are the reason for the error on the held-out comparisons not converging toward $0$ in Figure 2. \n\n**R: What is the number of available annotations for each dataset in figure 2?**\n\nThe number of available comparisons for each dataset is provided in Table 1 (located above Figure 2) under \"\\#comparisons\". \n\n* **ImageClarity** - 27 730\n\n* **WiscAds** - 9 528\n\n* **IMDB-WIKI-SbS** - 110 349\n\n**R: What is $\\Delta_*$? Is it $\\Delta_* = \\min_{ij} \\Delta_{ij}/|i-j|$?**\n\nYou are correct, $\\Delta_*$ should be defined as $\\Delta_* = \\min_{ij} \\Delta_{ij}/|i-j|$ and we will add an explicit definition. Note, that we in the proof of Thm 1 assume, w.l.o.g, that the items are indexed such that $i > j$ implies $y_i > y_j$. This means that $|i-j|$ is the distance between the elements in the ordered list. Hence, we can lower bound $\\Delta_{ij}$ by a constant times the difference in position in the ordered list. Substituting $\\Delta_{ij}$ by $\\Delta_* |i-j|$ in the lower bound on line 158 allow us to simplify that expression since all items in the sum now only depends on $\\Delta_* |i-j|$ and we can apply results for geometric sums. \n\n**R: Clarification regarding ''algorithms based only on preference feedback'' on line 74.**\n\nAs also pointed out by LY2M, this sentence can be improved. By \"based only on preference feedback\" we mean sorting algorithms that disregard attributes/features, regardless of whether they are present. This is the case for TrueSkill, and Figure 2d highlights its inability to generalize to new items. We will improve our formulation for the final version. For example, ''algorithms based only on preference feedback that ignore contextual information''.\n\n**R: I suggest adding the assumption on response (eq 2) and the $O(n^2)$ complexity to the list of limitations.**\n\nWe thank the reviewer for this suggestion and believe that while we have addressed the former limitation in our first answer above, and will add a discussion on complexity to the final version, both topics warrant being mentioned as potential future directions to explore further.\n\nWe thank tuDy for their suggestions for improving the text and have incorporated these into the updated manuscript. \n\n**References**\n\n* [1] Qian, et al. (2015). Learning user preferences by adaptive pairwise comparison.\n\n* [2] Canal, et al., (2019). Active embedding search via noisy paired comparisons.\n\n* [3] Houlsby, et al., (2011) Bayesian Active Learning for Classification and Preference Learning", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear reviewers and chairs, thank you for evaluating our work. 

We are happy that a majority of reviewers found that the reasons to accept this paper outweigh the reasons to reject it. As strengths, the reviews pointed to the importance of the problem (3/4 reviews), the theoretical justification for the proposed algorithms (4/4), and the empirical evaluation (3/4).
We also thank the reviewers for asking clarification questions and suggesting improvements to strengthen the paper. We have addressed these in individual rebuttals to each review and are ready to incorporate the arguments in the final manuscript. 
Moreover, we have attached a plot showing $R_{I_D}$ for the experiment in Figure 1b in the original paper, as requested by reviewer LY2M, for completeness.

Two reviewers asked about the computational complexity of the algorithms. We expand on this below but stress that sample complexity, not computational complexity, is the focus of this work. 

Two main factors impact the computational complexity of GURO. The first is the selection of the next comparison. When sampling according to (5), the bottleneck is the calculation of $\lVert z_{ij} \rVert_{H_{t-1}^{-1}}$ for every possible comparison, which scales according to $O(d^2n^2)$ where $n=$ number of items, and $d=$ dimension of the features. As covered in Appendix F, to speed up computations for IMDB-WIKI-SbS, we only evaluate a subsample of all possible comparisons every iteration. This resulted in no noticeable change in performance and is similar to the approach taken in [1]. When only looking at a sample of $m \ll n^2$ combinations this complexity is reduced to $O(d^2m)$. Another interesting direction could be to first evaluate the model uncertainty of individual item scores $\lVert x_{i} \rVert_{H_{t-1}^{-1}}$, and then only evaluate (5) for the $k$ items with the highest uncertainty, giving a complexity of $O(d^2kn)$.

The second factor is the update of model parameters. This is done by solving a logistic regression where the computational complexity of each iteration is $O(ds)$ where $s =$ the number of samples collected. Each iteration also includes updating the inverse Hessian using the Sherman-Morrison formula with a complexity of $O(d^2)$. An interesting benefit of BayesGURO is that it allows for sequential updates of $\theta$, avoiding having to solve the logistic regression using all previously collected samples (which are instead embedded into the prior).  

**References**

* [1] Canal, et al., (2019). Active embedding search via noisy paired comparisons. International Conference on Machine Learning.

Meta-review: The paper tackles the problem of learning to rank items based on a contextual scoring rule and item feature vectors, from noisy dueling feedback, in the pure exploration setting. The paper is well written and the problem tackled is especially relevant due to the recent popularity of the RLHF setting. The claims of the paper are supported by both novel theoretical results as well as an empirical evaluation.

The main weaknesses of the paper tied to its direct practical relevance. In particular, the algorithm does not show a substantial performance gain over existing baselines and given its computational complexity is scaling as $O(N^2d^2)$, it is not clear the approach would scale to the size of the datasets encountered in the settings modelled in the paper. The authors propose an alternative lower-complexity algorithm in their rebuttal but it is not accompanied by the same guarantees as the approach in the paper.

Nonetheless, it is my and the reviewer's opinion that the submission presents sufficient merit to warrant acceptance.
Decision: Accept (poster)