Active preference learning for ordering items in- and out-of-sample

Authors: herman  bergström
emil  carlsson
devdatt  dubhashi
fredrik d johansson
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-08 14:01:10

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.

Main paper: 
 introduction: 
 The success of supervised learning is built on annotating items at great volumes with small error. For subjective assessments, however, assigning a value from an arbitrary rating scale can 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 et al., 2022; Zhu et al., 2023) . Preference feedback is sufficient to learn an ordering of items (Fürnkranz and Hüllermeier, 2003) , but for n items, there are O(n 2 ) possible pairs of items to compare. A common solution is to use crowd-sourcing (Chen et al., 2013; Yang et al., 2021; Larkin et al., 2022) , but many tasks require domain expertise, making annotations expensive to 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 et al., 2024; Tärnåsen and Bergström, 2023) . So, how can we learn the best ordering possible from a limited number of comparisons?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) . However, consider a radiologist who wants to quantify the expression of a disease in a collection of X-ray images. Purely preference-based 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 a map from pairs of item contexts x i , x j (e.g., the contents of images) to the comparison i ≻ ? 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 a 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 et 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 to support efficient insample 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 implement in a greedy deterministic algorithm called GURO (Section 5). We further propose a 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 comparisons 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 parameters. This results in faster convergence in-sample, better generalization to new items, and efficient continual learning when new items are added.Question: Do the main claims made in the 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 contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
ordering items with active preference learning: 
 Our goal is to learn an ordering of items I according to an unobserved score y i ∈ R, defined for each item i ∈ I. The ground-truth ordering of I is determined by a comparison function π ij := 1[y i > y j ], where π ij = 1 indicates that i ranks higher than j. We assume there are no ties.We define the ordering error R I (h) of a learned comparison function h : I × I → {0, 1} as the frequency of pairwise inversions under a uniform distribution of item pairs,EQUATIONwhere n = |I|. This error is equivalent to the normalized Kendall's Tau distance (Kendall, 1948) .Hypotheses h are learned from preference feedback-noisy pairwise comparisons C ij ∈ {0, 1} for items (i, j) related to their score, for example, provided by human annotators. C ij = 1 indicates that an annotator perceived that item i has a higher score than j, i.e., that they prefer i over j. Our goal is to minimize the ordering error R I (h) for a fixed budget T ≥ 1 of adaptively chosen comparisons.We are interested in contextual problems, where each item i ∈ I is endowed with item-specific attributes x i ∈ X ⊆ R d . 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 I D ⊆ I and generalizing to I \ I D . 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 I D ⊆ I and item attributes x i for i ∈ I D . 2) Over rounds t = 1, ..., T , the learner requests a comparison of two items i t , j t ∈ I D according to a sampling criterion and Bandits: Bandit algorithms with relative or dueling feedback (Yue and Joachims, 2009; Bengs et al., 2021; Yan et 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, a contextual dueling bandit for regret minimization under linear stochastic transitivity, matching (2), and Di et al. (2023) gave varianceaware 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 a 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 reinforcement learning with human feedback (RLHF) (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 sample complexity of learning a 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 a 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).4 Which comparisons result in a good ordering?We give an upper bound on the ordering error R I (h) for a hypothesis h fit using a set of T comparisons. The bound is retrospective, attempting to answer the question "if we collect comparisons D T , how good is our resulting model at ordering the items in I?". In Section 5, we use insights from the result to design an active learning algorithm.We restrict our analysis to the logistic model in (2) and denote by R(θ) ≡ R I (h θ ) the risk of the hypothesis defined byh θ (i, j) = 1[θ ⊤ z ij > 0].Recall that z ij = x i -x j for i, j ∈ I, and define z t ≡ z itjt as the difference between attributes for the pair of items selected at round t. Let θ t be the maximum-likelihood estimate (MLE) fit to t rounds of feedback, D tθ t = arg max θ t s=1 c s log σ(θ ⊤ z s ) + (1 -c s )(1 -σ(θ ⊤ z s )) . (3) Let ∆ ij > 0 lower bound the margin of comparison, |σ(z ⊤ ij θ * ) -1/2| > ∆ ij for all i, j ∈ I and define ∆ * = min i̸ =j ∆ ij /|i -j|. Next, let H t (θ) := t s=1 σ(z ⊤ s θ)z s z ⊤s be the Hessian of the negative log-likelihood of observations at time t under (2), given the parameter θ, also known as observed Fisher information. We define Ht (θ) := 1 t H t (θ). For a square matrix V , we define ∥x∥ V =x ⊤ V x. We make the following assumptions for our analysis:Assumption 1. θ * satisfies ∥θ * ∥ 2 ≤ S for some S > 0.Assumption 2. ∀i ∈ I, we have∥x i ∥ 2 ≤ Q for Q > 0.Assumption 3. H T (θ T ) and H T (θ * ) have full rank and minimum eigenvalues larger than λ 0 > 0.Assumption 1 implies that θ * lies in some ball with radius S and cannot have unbounded coefficients. 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 assumptions 1 and 2 are standard in the bandit literature and only required for our analysis. Assumption 3 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 a burn-in phase of d samples in the beginning of an adaptive strategy. Assumption 3 ensures the uniqueness of θ t .We start by stating the following concentration result for the deviation of σ(z ⊤ ij θ T ) from the true probability σ(z ⊤ ij θ * ). The proof of Lemma 1 is found in Appendix C and builds on results for optimistic algorithms in logistic multi-armed bandits (Filippi et al., 2010; Faury et al., 2020) .Lemma 1 (Concentration Lemma). Define, for all pairs of items i, j ∈ I, and any ∆ > 0,α ij (∆) := exp -∆ 2 T 8dC 1 ( σ(z ⊤ ij θ T )∥z ij ∥ H-1 T (θ T ) ) 2 , β ij (∆) := exp -∆T dC 1 ∥z ij ∥ 2 H-1 T (θ T ).Then, if α := α ij (∆), β := β ij (∆) and α, β ≤ 1 4dT , P |σ(z ⊤ ij θ * ) -σ(z ⊤ ij θ T )| > ∆ ≤ 2dT (α + β) . C 1 depends on S, λ 0 , Q from Assumptions 1-3 (see Appendix C for definition and proof).The concentration result in Lemma 1 is verifiable (given by observables) since the upper bound depends only on the maximum likelihood estimate θ T at time T , not on θ * . We present a sharper, unverifiable bound in Appendix C which instead depends on θ * but does not suffer from the explicit scaling with d in the definitions of α and β. The bound in Lemma 1 can also be expressed in terms of H -1 T (θ T ) by using the equality||z ij || 2 H -1 T (θ T ) = 1 T ||z ij || 2 H-1 T (θ T ) .As long as our sampling strategy ensures that the minimum eigenvalue of Ht (θ t ) does not tend to zero, i.e., the strategy is strongly consistent (Chen et al., 1999) , we haveα ij (∆ ij ) ∼ exp[-∆ 2 ij T /( σ(z ⊤ ij θ T ) 2 ∥z ij ∥ 2 H-1 T (θ T ) )] and β ij (∆ ij ) ∼ exp[-∆ ij T /∥z ij ∥ 2 H-1 T (θ T ) ]. Since ∆ 2 ij < ∆ ij < 1/2by definition, we can view α as the first-order term and β as the second-order term of our bound. D t = D t-1 ∪ {i t , j t , c t )} 6: θ t = MLE(D t ) according to (3) [or θ t = MAP(D t )as in (11) in the Appendix] 7: end for 8: Return h T Lemma 1 formally captures the intuition that it should be easier to sort when annotations contain little noise, i.e., σ(z ⊤ ij θ T ) is small. Especially, we observe σ(z ⊤ ij θ T ) ≈ 0 for pairs where ∆ ij is sufficiently large, causing the first-order term to vanish, leaving us with the faster decaying second-order term β. Lemma 1 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, e.g., where annotators disagree or labels are noisy, captured by σ(z ⊤ ij θ T ), as well as high epistemic uncertainty captured by ||z ij || H-1 T (θ T ) . A direct consequence of Lemma 1 is the following bound on the ordering error of h θ T over I,E[R(θ T )] ≤ i̸ =j 2 min {2dT (α ij (∆ ij ) + β ij (∆ ij )) , 1} n(n -1) .The right-hand side in the above inequality can be bounded further by utilizing that ∆ ij ≥ |i-j|∆ * .Together with Markov's inequality, this yields the following bound on P (R(θ T ) ≥ ϵ).Theorem 1 (Upper bound on the ordering error).Let α * := max i̸ =j α ij (∆ * ) and β * := max i̸ =j β ij (∆ * ), with α, β from Lemma 1. Then, for α * , β * ≤ 1 4dT and any ϵ ∈ (0, 1), the ordering error R(θ T ) satisfiesP (R(θ T ) ≥ ϵ) ≤ 4dT ϵn α -1 * -1 -1 + β -1 * -1 -1 ≈ 4dT ϵn (α * + β * ) ,where α * and β * decay exponentially with T .Theorem 1 suggests that the probability of R(θ T ) ≥ ϵ decays exponentially with a rate that depends on the quantities max i,j σ(z⊤ ij θ T )∥z ij ∥ H-1 t (θ T ) and max i,j ∥z ij ∥ 2 H-1 t (θ T ). Both quantities are random variables that depend on the particular sampling strategy that yields H t . Focusing on the leading term, max i,j σ(z ⊤ ij θ T )∥z ij ∥ H-1 t (θ T ) , Theorem 1 suggests that an active learner should gather data to minimize this quantity and obtain the smallest possible bound. The factor ∥z ij ∥ 2 H-1 T (θ T ) is the weighted norm of z ij w.r.t. the inverse of the observed Fisher information (cf. Kirsch and Gal (2022) ). It controls the shape of the confidence ellipsoid around θ T and the width of the confidence interval around θ ⊤ T z ij . The leading term in Theorem 1 re-scales this quantity with aleatoric noise under the MLE estimate θ T . 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) applications to generalized linear models with other link functions, iii) lower bounds on the ordering error, and iv) an algorithm-specific upper bound.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 an online setting and the lack of optimality guarantees for our algorithm.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model wellspecification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-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 problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (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.• All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.• All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a 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. 
experimental result reproducibility: 
 Question: Does the paper fully disclose all the information needed to reproduce the main experimental 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)?Answer: [Yes] Justification: Among our main contributions are the GURO and BayesGURO sampling strategies, which we not only offer algorithmic descriptions of but also provide the code for. We also describe 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.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • 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 a 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) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome 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., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
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 σ(θ ⊤ z ij ) and return in Section 5.1 to parameterization variants to reduce the effects of model misspecification.The main component of the bound in Theorem 1 to be controlled by an active learner is the termEQUATIONwhich represents the highest uncertainty in the comparison of any items i, j ∈ I under the model θ T . A smaller value of (4) yields a smaller bound and a stronger guarantee. Recall that, for any t = 1, ..., T , θ t is the MLE estimate of the ground-truth parameter θ * with respect to the observed history D t . Both factors in (4) are determined by the sampling strategy that yielded the item pairs (i t , j t ) in D T and, therefore, H T and θ T (the results of comparisons c ij are outside the control of the algorithm, but z ij are known).Direct minimization of (4), for a subset I D , is not feasible without access to comparisons c ij and their likelihood under θ T . Instead, we adopt a greedy, alternating approach: In each round, a) a single pair is sampled for comparison by maximizing (4) under the current model estimate, and b) θ t is recomputed based on D t . Specifically, at t = 1, ..., T , we sample,EQUATIONWe refer to this sampling criterion as Greedy Uncertainty Reduction for Ordering (GURO), since it reduces the uncertainty of θ t in the direction of z ij . To see this, consider the change of H t (θ t ) after a single play of i t , j t . The Sherman-Morrison formula (Sherman and Morrison, 1950) yields,EQUATIONwhere z t := z itjt . With ξ as the second term in (6), it holds for all i < j ∈ I, withH t-1 = H t-1 (θ t-1 ), that ||z ij || 2 H -1 t (θt-1) = ||z ij || 2 H -1 t-1 -||z ij || 2 ξ ≤ ||z ij || 2 H -1 t-1. The inequality is strict for the pair i t , j t in (5). As θ t converges to θ * , this pair becomes representative of the maximizer of (4) provided there is no major systematic discrepancy between I D and I.Surprisingly, GURO can also be justified from a Bayesian analysis. Consider a Bayesian model of the parameter θ with p(θ) the prior belief and p(θ | D t ) the posterior after observing the preference feedback in D t . A natural active learning strategy is to sample items i t , j t for which the model preference is highly uncertain under the posterior distribution,EQUATIONwhere Vθ|Dt-1 [σ(θ ⊤ z ij )] is a finite-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(θ) and benefits from controlled stochasticity through the empirical estimate V, which makes it appropriate for batched algorithms-a 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 2 ) 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., 2011) . A way of mitigating this computational complexity is 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 only looking at a sample of m ≪ n 2 pairs, the complexity is reduced to O(m). While making m too small can hurt the sample complexity, we describe in Appendix E how we implemented this sub-sampling 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 it takes to query an annotator.Our default preference model h(i, j) = 1[f (i, j) > 0] is based on a fully contextual scoring functionEQUATIONfit with a logistic likelihood σ(f (i, j)) ≈ p(C ij = 1). The model's strength is that the variance in its estimates grows with d, but not with n = |I|, 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 I D span attributes observed for I.The limitations of a fully contextual model are model misspecification (error due to the functional form), and noise (error due to C not being fully determined by X). The former can be mitigated by applying the linear model to a representation function ϕ :X → R d ′ , f θ (x i , x j ) = θ ⊤ (ϕ(x i ) - ϕ(x j )).A good representation ϕ, 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 a different task can perform much better than a random initialization. 2Noise due to insufficiencies in X cannot be mitigated by a representation ϕ(x); If annotators consistently compare items based on features U not included in X, no function h(X i , X j ) can perfectly order the items. However, for in-sample ordering of I D , adding per-item parameters ζ i ∈ R to the scoring function, one for each item i ∈ I D , can mitigate both misspecification and noise,EQUATIONWe call this a hybrid model and apply it in "GURO Hybrid" and baselines in experiments. The term ζ i -ζ j 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 θ ⊤ ϕ(x i ) is nearly wellspecified. Using ζ i -ζ j alone is sufficient in-sample, but has high variance (the dimension is n instead of d) and poor generalization (ζ i are unknown for items i ̸ ∈ I D ). In practice, we use L2 regularization to prevent the model from learning an arbitrary θ by using the full expressivity of ζ i (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 ).Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: We provide the code in a 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 (https://nips.cc/public/ guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) 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 are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
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 annotators3 .We provide a 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 it 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-uncertainty pairs to get the order right. CoLSTIM (Bengs et al., 2022) is a contextual bandit algorithm, developed for regret minimization and is not expected to perform well here. It is 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 as a 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 a version of GURO called NormMin that ignores the σ(z ⊤ ij θ t ) term and plays the pair maximizing ∥z ij ∥ H -1 t (θt) , i.e., it minimizes the second-order term in Lemma 1. Nor-mMin corresponds to 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 comparison 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. Our first task (X-RayAge) is to order X-ray images based on perceived age (Ieki et al., 2022) where the preference feedback follows a (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 true age. Features were extracted using the 121-layer DenseNet in the TorchXrayVision package (Cohen et al., 2022) followed by PCA projection, resulting in 35 features. A ridge regression model, θ * , was fit to the true age (R 2 ≈ 0.67). During active learning, feedback is drawn from p(C ij = 1) = σ θ ⊤ * z i,j • λ , where λ (set to 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 1a shows the ordering error 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 a 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 (I D ) containing the youngest 50% and the other (I E ) 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 I E and I D are presented in Figure 1b . While all algorithms are worse at ordering items in I E , GURO and BayesGURO achieve the lowest average difference. Together with Figure 1a , this means that our proposed algorithms achieved the best in-sample and out-of-sample orderings. For completeness, the in-sample performance of algorithms in the generalization experiment in Figure 1b are included in Appendix E.2.Next, we evaluate our algorithm on three publicly available datasets to study the algorithms' performance when preference feedback comes from human annotators (see Table 1 for an overview, detailed information of datasets in Appendix E.1). The datasets are IMDB-WIKI-SbS (Pavlichenko 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 Table 1 : Datasets with preference feedback from annotators. Pretrained models are ResNet34 (He et al., 2016) , all-mpnet-base-v2 (Reimers and Gurevych, 2019) , and FaceNet (Schroff et al., 2015) opponent. In all datasets, pairs of items were sampled uniformly for annotation. For each experiment, we construct a feature vector ϕ(x i ) ∈ R d 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 to have an objective ground truth ordering but this is not the case for WiscAds or IMDB-WIKI-SbS. As the ground-truth ordering is generally unknown also in real-world applications, we evaluate methods by the error on a heldout set of comparisonsD ′ , RD ′ (h) = 1 |D ′ | (i,j,c)∈D ′ 1[h(i, j) ̸ = c].This serves as an empirical analog of Kendall's Tau distance and a minimizer of RD ′ (h) will minimize R I (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 to all available comparisons, see e.g., Maystre and Grossglauser (2017) . In Appendix E.2, 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 to 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 easiest 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 error. Figures 2b and 2c highlight the differences between modeling strategies. The fully contextual algorithms initially improve rapidly, achieving a 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 a 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 TrueSkill 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 a few-shot scenario where after some time, additional images are added to the pool of items. IMDB-WIKI-SbS was used as it contained the highest number 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 is very slight, likely a result of added samples being drawn from the same distribution. For TrueSkill, the error 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 a rough ranking of the out-of-sample elements using the contextual features.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 means 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 be provided either with the code, in appendix, or as supplemental material. 
conclusion: 
 We have demonstrated the benefits of utilizing contextual features in active preference learning to efficiently order a list of items. Empirically, this leads to quicker convergence, compared to noncontextual methods, and allows algorithms to generalize out-of-sample. We derived an upper bound on the ordering error and used it to design an active sampling strategy that outperforms or matches 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.The optimality of our sampling strategy remains an open question. A future direction is to derive a lower bound on the ordering error, and prove an-ideally matching-algorithm-specific upper bound. However, constructing upper bounds for related fixed-budget tasks is an open problem (Qin, 2022) . Moreover, motivated by the annotation setting, our focus has been on reducing sample complexity 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 to a limited amount of already-collected (offline) human preference data, causing different algorithms to select disproportionately similar comparisons. Future work should evaluate the strategies in an online setting. Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: In Section 6 we either provide 1-sigma error bars or the 95% confidence interval, explicitly stating which in the figure captions. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]• According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?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 in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: x i ∈ R d Context attributes for item i ∈ I z ij ∈ R d z ij = x i -x j for i, j ∈ I y i Score for item i ∈ I c t ∈ {0, 1}The outcome of the comparison at time t,1 if i t was preferred to j t D t D t = ((i 1 , j 1 , c 1 ), ..., (i t , j t , c t )) θ ∈ R d Model parameter θ * ∈ R dModel parameter of the environmentθ t ∈ R dEstimated parameter at time t σ(.)Sigmoid (logistic) function σ(.)derivative of σ(.)H t (θ)Hessian of the negative log-likelihoodH t (θ) := t s=1 σ(z ⊤ s θ)z s z ⊤ s Ht (θ)Hessian normalized by number of plays Ht (θ) := 1 t H t (θ) θ B,t ∈ R dThe MAP estimate of θ at time t H B,tThe Hessian in the Bayesian setting, adjusted by the prior covariance H -1 B,0∥z ij ∥ H -1 t (θ) ∥z ij ∥ H -1 t (θ) = z ⊤ ij H -1 t (θ)z ij h Comparison model (binary output) fComparison logit (typically linear), e.g.,f θ (i, j) = θ ⊤ (x i -x j )The log-likelihood Lt(θ) of data Dt = {(is, js, cs)} t s=1 , with zs = xi s -xj s , under a logistic regression model with parameters θ is defined byLt(θ) = t s=1 cs log σ(θ ⊤ zs) + (1 -cs)(1 -σ(θ ⊤ zs)) .The maximum likelihood estimator (MLE) at time t is the parametersEQUATION)The regularized estimator with ridge/ℓ2 penalty with parameter λ isθ R t = arg min θ -Lt(θ) + λ∥θ∥ 2 2 .B.2 Bayesian estimator for logistic regression θB,t is the MAP estimate of θ at time t according to the log likelihoodEQUATIONwhereln p(θ | Dt) = - 1 2 (θ -θB,0) ⊤ H -1 B,0 (θ -θB,0) + t ct ln(σ(z ⊤ i t ,j t θ)) + (1 -ct) ln(1 -σ(z ⊤ i t ,j t θ)) + const.The hessian at time t is defined as HB,t = HB,0 + (i,j)∈D t σ(z ⊤ i,j θB,t)zi,jz ⊤ i,j = HB,0 + Ht.Moreover, if priors θB,0 = 0 and H -1 B,0 = I d are used, the log likelihood boils down to:ln p(θ | Dt) = - 1 2 ||θ|| 2 2 + t ct ln(σ(z ⊤ i t ,j t θ)) + (1 -ct) ln(1 -σ(z ⊤ i t ,j t θ)) + constwhich implies that the MAP estimate will be the same as the MLE estimate with ridge regularisation in the frequentist setting. Similarly, the Hessian becomes:HB,t = Ht + I dSequential 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 HB,t depends on the current estimate of θB,t.We describe BayesGURO, a Bayesian sampling criterion, closely related to GURO. Consider a Bayesian model of the parameter θ with p(θ) the prior belief and p(θ | Dt) the posterior after observing the preference feedback in Dt. A natural strategy for learning more about the ordering of I is to sample items it, jt based on an estimate of the posterior variance of predictions for their comparison,EQUATIONHere, Vθ|D t [σ(θ T zij)] is an estimate of the variance of probabilities σ(θ T zij), computed from finite samples drawn from the posterior of θ. Estimating the variance in this way both i) allows for tractable implementation, and ii) induces controlled stochasticity in the selection of item pairs. This can be 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 θ is updated. We refer to the sampling criterion in (7) as BayesGURO.For the logistic model considered in Section 4, using Laplace approximation with a Normal prior N (0, H -1 B,0 ) on θ, the Bayesian criterion in ( 7) is related to the GURO sampling criterion in (5) through the first-order Taylor expansion of the variance:V θ|D t (σ(θ ⊤ zij)) ≈ ( σ(E θ|D t [θ ⊤ zij])) 2 V θ|D t [θ ⊤ zij] = ( σ(θ ⊤ B,t zij)||zij|| H -1 B,t (θ B,t ) ) 2 ,where θB,t is the MAP estimate of θ at time t and HB,t is the Hessian adjusted by the prior covariance H -1 B,0(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(θ), which could be useful under strong domain knowledge, and the stochasticity of using few posterior samples to approximate V make the two criteria distinct.The uniform sampling algorithm is given in Algorithm 2. The corresponding Bayesian version replaces line 5 with the MAP estimate.Algorithm D t = D t-1 ∪ {i t , j t , c t )} 5: Let θ t = MLE(D tDraw (i t , j t ) = arg max i,j H[y | z i,j , D t-1 ] -E θ∼p(θ|Dt-1) [H[y | z i,j , θ]] 4:Observe c t from noisy comparison (annotator) 5: D t = D t-1 ∪ {i t , j t , c t )} 6: Let θ t = MAP(D t ) 7: Update H B,t ← H B,0 + (i,j)∈Dt σ(z ⊤ i,j θ t )z i,j z ⊤ i,The BALD criteria formalized using our notation becomesarg max i,j H[y | zi,j, Dt] -E θ∼p(θ|D t ) [H[y | zi,j, θ]],where H represents Shannon's entropyh(p) = -p log 2 (p) -(1 -p) log 2 (1 -p).The first term of the equation becomesH[y | zij, Dt] = h(Pr(y | zi,j, Dt)) = h Pr(y | zi,j, θ) Pr(θ | Dt)dθ .Here Pr(y | zi,j, Dt) is the predictive distribution for our Bayesian logistic regression model. As covered in Bishop and Nasrabadi (2006, Chapter 4) , this expectation cannot be evaluated analytically but can be approximated using the probit function Φ;Pr(y | zij, Dt) ≈ Φ   θ ⊤ t zi,j λ -2 + ||zij|| 2 H -1 t   ≈ σ     θ ⊤ t zi,j 1 + π||z ij || 2 H -1 t (θ * ) 8     .Next, the term E θ∼p(θ|D t ) [H[y | zi,j, θ]] must be calculated. The true definition isE θ∼p(θ|D t ) [H[y | zi,j, θ]] = h(σ(θ ⊤ zi,j))N (θ | θt, H -1 t )dθ.To make this a one variable integral, let X = θ ⊤ zi,j define a new random variable. Since θ ∼ N (θt, H -1 t ), and zi,j is a constant vector, we know that X will follow a univariate normal distribution X ∼ N (θ ⊤ t zi,j, ||zij|| 2H -1 t). This allows us to rewrite the integral ash(σ(θ T z))N (θ | θt, H -1 t )dθ = h(σ(x))N (θ ⊤ t zi,j, ||zij|| 2 H -1 t )dx.However, this integral has no closed form solution. Instead we perform the same strategy as in Houlsby et al. (2011) and do a Taylor expansion of ln h(σ(θ ⊤ z)). The third-order Taylor expansion gives ush(σ(x)) ≈ exp - x 2 8 ln 2 .Inserting this, the term can be approximated ash(σ(x))N (x | θ ⊤ t zi,j, ||zij|| 2 H -1 t )dx ≈ exp - x 2 8 ln 2 N (x | θ ⊤ t zi,j, ||zij|| 2 H -1 t )dx = C ||zij|| 2 H -1 t + C 2 exp   - (θ ⊤ t zi,j) 2 2(||zij|| 2 H -1 t + C 2 )   ,where C = √ 4 ln 2. Finally, we arrive at an estimation of the objective function we wish to maximize:H[y | zi,j, Dt] -E θ∼p(θ|D t ) [H[y | zi,j, θ]] ≈ h   σ   θ ⊤ t zi,j 1 + π 8 ||zij|| 2 H -1 t     - C ||zij|| 2 H -1 t + C 2 exp   - (θ ⊤ t zi,j) 2 (||zij|| 2 H -1 t + C 2 )  Proof. We now proceed to boundP |σ(z ⊤ ij θt) -σ(z ⊤ ij θ * )| > ∆ .From the self-concordant property of logistic regression we have (Faury et al., 2020 )|σ(z ⊤ ij θt) -σ(z ⊤ ij θ * )| ≤ σ(zij⊤θt)|z ⊤ ij (θt -θ * )| + 1 4 |z ⊤ ij (θt -θ * )| 2 .We will prove a high probability bound on the eventEQUATION)Directly trying to bound the LHS in Equation 13will result in a rather messy expression. Instead, we define the eventsE1 := σ(zij⊤θt)|z ⊤ ij (θt -θ * )| ≤ ∆ 2 E2 := 1 4 |z ⊤ ij (θt -θ * )| 2 ≤ ∆ 2 .Clearly E1 E2 implies the expression in Equation 13. Assume we have bounds on the complement of these events, P (E c 1 ) ≤ α andP (E c 2 ) ≤ β. Then P |σ(z ⊤ ij θt) -σ(z ⊤ ij θ * )| > ∆ ≤ α + β + αβ ≤ 2α + 2β.We now proceed to bound the probability of these complements separately.Step 1. Relating θt to θ * : The first challenge in our analysis to is relate θ * and θt. In contrast to linear regression, where we have a closed-form expression for θt, there is no analytical solution for θt given a set of observation. However, we know that θt is the MLE, corresponding toθt = arg max θ Lt(θ)whereLt(θ) = t s=1 cs log σ z ⊤ s θ + (1 -cs) log 1 -σ z ⊤ s θ .We have∇ θ Lt(θ) = t s=1 cszs - t s=1 σ z ⊤ s θ zs g t (θ)and hence gt(θt) = t s=1 cszs. A standard trick in logistic bandits (Filippi et al., 2010; Faury et al., 2020; Jun et al., 2021) is to relate θ * -θt to gt(θ * ) -gt(θt). Especially, the following equality is due to the mean-value theorem (see Filippi et al. (2010) )gt(θ * ) -gt(θt) = Ht(θ ′ ) (θ * -θt) (14)where θ ′ is some convex combination of θ * , θt. Note that Ht(θ ′ ) has full rank.Using Equation 14 yieldsz ⊤ ij (θ * -θt) = z ⊤ ij H -1 t (θ ′ ) (gt(θ * ) -gt(θt))Furthermore, since gt(θt) = t s=1 cszs, due to ∇ θ Lt(θt) = 0, we havegt(θt) -gt(θ * ) = t s=1 cs -σ z ⊤ s θ * ϵs zswhere ϵs is a sub-Gaussian random variable with mean 0 and variance ν 2 s := σ z ⊤ s θ * . We defineSt := t s=1ϵszs.We now havez ⊤ ij (θ * -θt) = z ⊤ ij H -1 t (θ ′ )Stand Lemma 10 in Faury et al. (2020) states that H -1 t (θ ′ ) ≼ (1 + 2S)H -1 t (θ * ) where ||θ * ||2 ≤ S. Hence,z ⊤ ij (θ * -θt) ≤ (1 + 2S) z ⊤ ij H -1 t (θ * )StStep 2. Tail bound for vector-valued martingales:We will now prove an upper bound on the probability that z ⊤ ij H -1 t (θ * )St deviates much from a certain threshold. This step is based on the proof of Lemma 1 in Filippi et al. (2010) which itself is based on a derivation of a concentration inequality in Rusmevichientong and Tsitsiklis (2010) . The difference compared to Filippi et al. ( 2010) is that we work with the Hessian Ht(θ * ) instead of the design matrix for linear regression Vt = s xsx ⊤ s . This require us to construct a slightly different martingale. Let A and B are two random variables such thatE exp γA - γ 2 2 B 2 ≤ 1, ∀γ ∈ R (15)then due to Corollary 2.2 in de la Peña et al. ( 2004) it holds that ∀a ≥ √ 2 and b > 0EQUATION)Let η ∈ R d and consider the processEQUATIONWe will now proceed to prove that M γ t (θ, η) is a non-negative super martingale satisfying Equation 15. Note thatγη ⊤ St -γ 2 ||η|| 2 H t (θ * ) = t s=1 γη ⊤ zsϵs -σ(θ ⊤ zs)γ 2 η ⊤ zs 2 Fs = t s=1Fs.Further we use the fact that ϵs is sub-Gaussian with parameter νs, .i.e,E [exp{λϵs}] ≤ exp ν 2 s λ 2 , ∀λ > 0. Let Ds-1 denote the observations up until time s, then E [exp{Fs} | Ds-1] = E   exp    γη ⊤ zs λ ϵs      exp      -σ(θ ⊤ t zs) ν 2 s γ 2 η ⊤ zs 2      ≤ exp ν 2 s λ 2 exp -ν 2 s λ 2 = 1. This also implies E [M γ t (θ * , η) | Dt-1] ≤ M γ t-1 (θ * , η) and M γ t (θ * , η) is a super-martingale satisfying E exp γη ⊤ St -γ 2 ||η|| 2 H t (θ * )≤ 1, ∀γ ≥ 0 and we can apply the results of de la Peña et al. (2004) .We now follow the last step of the proof of Lemma 1 in Filippi et al. (2010) . We let a = 2 log 1 δ for some δ ∈ (0, 1/e) and let b = λ0∥η∥ 2 2 . We have with probability at least 1 -δ|η ⊤ St| ≤ 2 log 1 δ ∥η∥ 2 H t (θ * )+λ 0 ∥η∥ 2 2 1 + 1 2 log 1 + ∥η∥ 2 H t (θ * ) λ0∥η∥ 2 2 .Rearanging and using the fact that λ0||η|| 2 2 ≤ ∥η∥ 2 H t (θ * ) ≤ t∥η∥2 yieldsEQUATION)where ρ is defined asρ(λ0) = 3 + 2 log 1 + 4Q 2 λ0 .We take Mt to be a matrix such that M 2 t = Ht(θ * ) and note that for any τ > 0P ||St|| 2 H -1 t (θ * ) ≥ dτ 2 ≤ d i=1 P S ⊤ t M -1 t ei ≥ τwhere ei is the i:th unit vector. Equation 18with η = M -1 t ei together with ||M -1 t ei|| H t (θ * ) = 1 yield that the following holds with with probability at least 1 -δEQUATION)Step 3. (Unverifiable) High-probability bounds on E1 and E2.We now have enough machinery to state high-probability bounds for our two events. These bounds will be unverifiable in the sense that the depend on the true parameter θ * which is not known to us during runtime. We derive verifiable bounds in the next step of the proof.Recall that H -1 t (θ * ) is symmetric. We apply Equation 18with η = H -1 t (θ * )zij and α > 0 in place of δ. First, we note thatEQUATIONWe solve for smallest possible α ∈ (0, 1/e) such that(1 + 2S)ρ(λ0) σ(z ⊤ ij θ * )||zij|| H -1 t (θ * ) 2 log t α ≤ ∆ 2Rearanging yieldsEQUATION)For E2 and the bound on its probability, β > 0 we haveEQUATION)Note that both Equation 21 and Equation 22 are under the assumption that the RHS satisfy < 1/e since this is required in order to apply the results of de la Peña et al. ( 2004). As we discuss in the main text, these quantities are approaching zero as O(T e -T ), ignoring various constants, for reasonable sampling strategies and will satisfy this condition eventually.Step 4. (Verifiable) High-probability bounds on E1 and E2.The bounds in the previous step depend on the true parameter θ * which we do not have access to in practise. We again use Lemma 10 of Faury et al. (2020) together with Cauchy-Schwartz|zij(θ * -θt)| = z ⊤ ij H -1/2 t (θ ′ )H 1/2 t (θ ′ )St ≤ (1 + 2S)||zij|| H -1 t (θ t ) ||St|| H -1 t (θ * ) .Using Equation 19we have with probability at last 1 -α(1 + 2S)σ(z ⊤ ij θ * )||zij|| H -1 t (θ t ) ||St|| H -1 t (θ * ) ≤ (1 + 2S) σ(z ⊤ ij θ * )||zij|| H -1 t (θ t ) ρ(λ0) 2d log t log d α .(23)We solve for smallest α ∈ (1/e) such that Equation 23 is smaller than ∆ij/2. This yieldsα ≤ exp      -∆ 2 8dρ 2 (λ0)(1 + 2S) 2 σ(z ⊤ ij θT )||zij|| H -1 t (θ T )) 2 + log dT     .Same steps for β yieldsβ ≤ exp      -∆ dρ 2 (λ0)(1 + 2S) 2 ||zij|| H -1 t (θ T )) 2 + log dT      . For brevity, define C1 = ρ 2 (λ0)(1 + 2S) 2 .Using the definition of Ht yields the statement of Lemma 1.Proof. We let i ≻ j denote that i is preferred to j. W.l.o.g assume 1 ≻ 2 ≻ ... ≻ n. The key observation is thatfor any i and j such that i < j it holds that ∆i,j > (j -i)∆ * .If we get the wrong relation between i, j then σ(z⊤ ij θ * ) -σ(z ⊤ ij θT ) > (j -i)∆ * . Lemma 1 implies P (σ(z ⊤ ij θ * )-σ(z ⊤ ij θT ) > (j -i)∆) ≤ dT (exp      -(j -i)∆ 2 8dρ 2 (λ0)(1 + 2S) 2 σ(z ⊤ ij θT )||zij|| H -1 t (θ T )) 2      α j-i ij + exp      -(j -i)∆ dρ(λ0)(1 + 2S) 2 ||zij|| H -1 t (θ T )) 2      β j-i ij).Let R(θT ) be the ordering error of the n items. Then, under a uniform distribution over items we haveE[R(θT )] ≤ 4dT n(n -1)       n-1 i=1 n j=i+1 α j-i ij A + n-1 i=1 n j=i+1 β j-i ij B       (24)A and B will be upper bounded using the same argument. We now upper bound sum ALet α * := exp -∆ 2 * 8dC 1 max i,j σ(z ⊤ ij θ T )||z ij || 2 H -1 t (θ * ) then A ≤ n-1 i=1 n j=i+1 α j-i * ≤ (n -1) n j=0 α j * -1 ≤ (n -1) 1 1 -α * -1 .This follows from the definition of δ1, * and properties of the geometric sum. It is easy to see that 1 1-e -x -1 =1 e x -1 . Hence, 4dT n(n -1) A ≤ 4dT n α -1 * -1 -1 .For B we perform the same steps with β * := exp-∆ * dC 1 max i,j ||z ij || 2 H -1 t (θ * ) to get 4dT n(n -1) A ≤ 4dT n β -1 * -1 -1 .Combing yields andE [R(θT )] ≤ 4dT n α -1 * -1 -1 + β -1 * -1 -1By Markov's inequality we haveEQUATION)Regularized estimators. In our analysis in Section 4, we have assumed that θT is the maximum likelihood estimate and that H(θT ) has full rank. This can be relaxed by considering ℓ2 (Ridge) regularization where θ λ 0 ,T is the optimum of the regularized log-likelihood with regularization λ0I andH λ 0 (θ λ 0 ,T ) = T s=1 σ(z ⊤ s θ λ 0 ,T )zsz ⊤ s + λ0I.The same machinery used to prove Lemma 1 (Filippi et al., 2010; Faury et al., 2020) can be applied to this regularized version with small changes to the final bound.Generalized linear models. It is also possible to derive similar results for generalized linear models with other link functions, µ(z ⊤ ij θ * ), by using the general inequalityH(θ) ≥ κ -1 V with V = T s=1 zsz ⊤ s and κ ≥ 1/ minz ij μ(z ⊤ ij θ * ).We conjecture that this will yield a scaling of ∼ exp(-∆ 2 T /κ) where, unfortunately, κ might be very large. For a more thorough discussion on the dependence on κ in generalized linear bandits, see Lattimore and Szepesvári (2020, Chapter 19) .Lower and algorithm-specific upper bounds on the ordering error. A worst-case lower bound on the ordering error can be constructed in the fixed-confidence setting, where the goal is to minimize the number of comparisons until a correct ordering is found with a given confidence, by following Garivier and Kaufmann (2016) . This involves defining the set of alternative models Alt(θ * ) which differs from θ * in their induced ordering of I. 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 out of the paper as we find it uninformative in the regime when the number of comparisons is small, (see Simchowitz et al. (2017) for a discussion on the limitations of these asymptotic results in the standard bandit setting). Constructing a lower bound for our fixed-budget setting, of learning as good an ordering as possible with a fixed number of comparisons, is much more challenging. The fixed-confidence result yields a bound for the fixed-budget case (Garivier and Kaufmann, 2016) , but constructing either a tight lower bound or a tight algorithm-specific upper bound is an open problem (Fang, 2022).Bengs et al. ( 2022) considered a problem formulation where the goal is to learn a parameter θ which determines the utility Yi,t for a set of arms i = 1, ..., n as a function of observed context vectors xi,t in a sequence of rounds t = 1, ..., T , Yi,t = θ ⊤ Xi,t . The probability that item i is preferred over j (denoted i ≻ j) in round t is decided through a comparison function F , Pr(i ≻ j | Xi,t, Xj,t) = F (Yi,t -Yj,t) . The goal in their setting is to, in each round, select two items (it, jt) 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ℜBSH = E[ T t=1 2Y i * t ,t -Yi t ,t -Yj t ,t] .Proposition 1 (Informal). An algorithm which achieves minimal regret in the setting of Bengs et al. (2022) can perform arbitrarily poorly in our setting.Proof. The optimal choice of arm pair in the BSH setting is the optimal and next-optimal arm (i * t , i ′ t ) such that i * t ≻ i ′ t ≻ j for any other arms j. Assume that the ordering of all other arms j is determined by a featureXj,t(k) but that X i * t ,t (k) = X i ′ t ,t (k).Then, no knowledge will be gained about arms other than the top 2 choices under the BSH regret. As 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 a lower bound under Gumbel noise. Saha and Krishnamurthy (2022) investigated where there is a computationally efficient algorithm that achieves the derived optimality guarantee.For BayesGURO and BALD, the posterior p(θ | Dt) 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-likelihood. For both methods, the priors θB,0 = 0 d and H -1 B,0 = I d were used, and sequential updates were performed every iteration. The sample criterion for BALD under a logistic model is given in Appendix B.5.1. For BayesGURO, 50 posterior samples were used to estimate Vθ|D t [σ(θ T zij)] for every zij. The hybrid algorithms follow the same structure with the added constraint that each per-item parameter ζi is independent of other parameters. This allows for efficient updates of H -1 B,t by using sparsity in the covariance. GURO, CoLSTIM, and Uniform use LogisticRegression from Scikit-learn (Pedregosa et al., 2011) with default Ridge regularization (C = 1) and the lbfgs optimizer. The former two updates θt every iteration using the full history, Dt in all experiments except for IMDB-WIKI-SbS, where GURO updates θt every 25th iteration. This caused no noticeable change in performance as GURO still updates H -1 t every iteration using the Sherman-Morrison formula. Note that when using the Sherman-Morrison formula in practice, you only get an estimate of H -1 t (θt) since previous versions have been calculated using older estimates of θ. This method for approximating the inverse hessian is covered in Bishop and Nasrabadi (2006, Chapter 5 ) and when we compared it to calculating H -1 t (θt) from scratch every iteration we observed that the methods performed equally. The design matrix for CoLSTIM is updated as in Bengs et al. (2022) : the confidence width c1 was chosen to be d log(T ), and the perturbed values were generated using the standard Gumbel distribution.To increase computational efficiency for the large IMDB-WIKI-SbS 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 a large speed-up and no noticeable change in performance during evaluation.ImageClarity Data available at https://dbgroup.cs.tsinghua.edu.cn/ligl/crowdtopk. 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 is the same for all images, the dataset has a true ordering with regards to the strength of the distortion applied.WiscAdds Data available at https://dataverse.harvard.edu/dataset.xhtml?persistentId= doi:10.7910/DVN/0ZRGEE (license: CC0 1.0). The WiscAdds dataset, containing 935 political texts, has been extended with 9 528 pairwise comparisons by Carlson and Montgomery (2017) . In comparisons, annotators have stated which of two texts has a more negative tone toward a political opponent. To extract general features from the text, sentences were embedded using the pre-trained all-mpnet-base-v2 model from the Sentence-Transformers library (Reimers and Gurevych, 2019) . After applying PCA to the sentence embeddings, each embedding had a dimensionality of d = 162.IMDB-WIKI-SbS Data available at https://github.com/Toloka/IMDB-WIKI-SbS (license: CC BY).IMDB-WIKI-SbS consists of close-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 a resolution lower than 160 × 160 were removed, resulting in 6 072 images and 110 349 comparisons. We extract features from each image using the Inception-ResNet implemented in FaceNet (Schroff et al., 2015) followed by PCA, resulting in d = 75 features per image.To highlight the importance of the first-order term in Lemma 1, we evaluated NormMin on the same X-ray ordering task as in Figure 1a . 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 completeness, we include Figure 3b which shows the in-sample error, RI D , during the generalization experiment.In this setting, 100 synthetic data points were generated. Each data point consisted of 10 features, where the feature values were sampled according to a standard normal distribution. The true model, θ * , was generated by sampling each value uniformly between -3 and 3. The pairwise comparison feedback was simulated the same way as in Section 6.1, with λ = 0.5. The upper bound of the probability that R(θt) ≥ 0.2 was calculated every iteration according to Theorem 1. Each algorithm was run for 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. As discussed in Section 6.2, the performance of our contextual approach will depend on the quality of the representations. To underscore the practical usefulness of our algorithms, we have performed the same experiment as in Figure 2c , but this time the model used to extract image features was untrained (i.e., the weights were random). As to be expected, the results, shown in 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. The ImageClarity dataset consists of multiple versions of the same image, with the same distortion applied to it 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 as in Figure 2a , but instead of evaluating on a holdout comparison set, we measure the distance to the ground-truth ordering.The overall results are very similar, although we do see a slight increase in the performance of contextual algorithms compared to the non-contextual TrueSkill. 2a , but now measuring the distance to the ground-truth ordering. Averaged over 25 seeds along with the 1-sigma error region.An alternate approach to evaluate ordering quality is to estimate a "ground-truth" ordering by applying the popular Bradley-Terry (BT) model (Bradley and Terry, 1952) to all 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 as in Figure 2 , but instead measure the distance to the constructed BT ordering. The overall trends remain, but for (b) and (c) there is a 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 to the maximum likelihood estimate of the BT model will be favored. To exemplify this we use the ImageClarity dataset since it contains the largest number of comparisons relative to the number of items. We sample 1 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 a second, more probable ordering, from the BT estimate using all 27 730 available comparisons. Figure 8 shows the distance between the GURO and TS algorithms and the different target orderings, where dashed lines indicate the distance to the ordering generated using the full list of comparisons. If 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 we instead measure the distance to the more probable order-NeurIPS Paper Checklist• 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 intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.It 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://github.com/Healthy-AI/GURO 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

One 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.
questions: 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]
- 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?
- 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?
- 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$
- 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.
- 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
- 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?
- 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$
- figure 2 would benefit from a log y scale - it is very difficult to discern between methods

Minor:
- line 147 uses the notation $\widehat{H}$ instead of $\widetilde{H}$. I assume this is a typo
- missing left parentheses in line 5 of GURO algorithm
- the word BayesGURO in Algorithm 1 should also probably be colored green to show the association to (7) and (11)
- be careful with red and green as distinguishing colors for readers with color vision deficiency
- fix quotes on line 258
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: --The assumption 1 and 2 are not so intuitive. It is better to illustrate an example.

--Baseline methods are weak. Though many related studies are mentioned in the related work section, performances of baselines are not shown in the experiments.

--The number of comparisons is  not reduced tremendously on the ImageClarity in Table1.

--Performances should be emphasized in terms of the prediction ordering quality.
questions: questions: State-of-the-art baselines should be added for performance comparison.
limitations: limitations: Limitation should be added.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
And 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.
questions: questions: Please provide more discussion on how difference the proposed method is comparing to logistic bandits.
limitations: limitations: Yes, the authors touch upon the limitation in the conclusion section.
paper_summary: paper_summary: This paper proposes an active learning algorithm for selecting pairs of items for comparison in order to learn a ranking of the items.
The 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.
strength_weakness: strength_weakness: * 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.

* 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.
questions: 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?

* 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?

Minor:
* 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: limitations: I suggest adding the assumption on response (eq 2) and the $O(n^2)$ complexity to the list of limitations.

Comments: comment: Thank you for the clarifications.
Thank you for your response. I am satisfied with these points and leave my review unchanged (at an 8). Also, please double check the definition of $\Delta_*$ in line 125. It is missing the quotient you defined above. It just says $\Delta_* = \min_{ij} \Delta_{ij}$