Optimal Design for Human Preference Elicitation
Authors: Subhojyoti Mukherjee
Anusha Lalitha
Kousha Kalantari
Aniket Anand Deshmukh
Ge Liu
Yifei Ma
Branislav Kveton
Venue: NeurIPS 2024 poster (2024)
Keywords: optimal design
active learning
preference elicitation
human feedback
learning to rank
Primary area: active_learning

Abstract: Learning of preference models from human feedback has been central to recent advances in artificial intelligence. Motivated by the cost of obtaining high-quality human annotations, we study efficient human preference elicitation for learning preference models. The key idea in our work is to generalize optimal designs, an approach to computing optimal information-gathering policies, to lists of items that represent potential questions with answers. The policy is a distribution over the lists and we elicit preferences from them proportionally to their probabilities. To show the generality of our ideas, we study both absolute and ranking feedback models on items in the list. We design efficient algorithms for both and analyze them. Finally, we demonstrate that our algorithms are practical by evaluating them on existing question-answering problems.

Optimal Design for Human Preference Elicitation
Subhojyoti Mukherjee University of Aesconsin-Maddione smukherjee270 2eweee77@wwsc..o edu
Anusha Lalitha AWS AI Labs
Kousha Kalantari AWS AT Labs
Aniket Deshmukh AWS Al Labs
Ge Liu UlUC
Yifei Ma AWS Al Labs
Branislav Kveton Adobe Research
Abstract
Learning of preference models from human feedback has been central recent advances in artificial intelligence. Motivated by the cost of obtaining high-quality human annotations, we study efficient human preference elicitation for learning preference models. The key idea our work is to generalize optimal designs, approach to computing optimal information gattrrrng policies, to lists items that represent potential questions with answers. The policy is distribution over the lists and we elicit preferences from them proportionally to their probabilities. To show the generality of our ideas, study both absolute and ranking feedback models on items in the list. We design efficient algorithms for both and analyze them. Finally, demonstrate that our algorithms are practical by evaluating them on existing question-anssee answering problems.
1 Introduction
Reinforcement learning from human feedback (RLHF) has been effective in aligning and fine-tuning large language models (LLMs) [68, 36, 15, 77, 39]. The main difference from classic reinforcement learning (RL) [81] is that the agent learns from human feedback, which is expressed as preferences for different potential choices [2. 49, 71, 10. 90]. The human feedback allows LLMs be adapted beyond the distribution of data that was used for their pre- pre-training and generate answers that are more preferred by humans [15]. The feedback can be incorporated by learning a preference model. When the human decides between two choices, the Bradley-Tery Terry-Luce (BTL) model [12] can be used. For multiple choices, the Plackett-Luce (PL) model [65, 54] can be adopted. good preference model should correctly rank answers to many potential questions. Therefore, learning of good preference model can be viewed as learning to rank, and we adopt this view in this work. Learning to rank has been studied extensively in both offline [14] and online [67, 43, 83, 80, 46) settings.
To effectively learn preference models, we study efficient methods for human preference elicitation. We formalize this problem as follows. We have a set of L lists representing questions, each with K items representing answers. The objective of the agent is to learn to rank all items in all lists. The agent can query humans for feedback. Each query is question with K answers represented as list. The human provides feedback on it. We study two feedback models: absolute and ranking. In the absolute feedback model, a human provides noisy feedback for each item in the list. This setting is motivated by how annotators assign relevance judgments in search [30, 57]. The ranking feedback motivated by learning reward models in RLHF [68, 36, 15, 77, 39]. In this model, human ranks all items the list according their preferences. While K is arguably the most common case, we study K > 2 for the sake of generality and allowing higher-capacity communication channel with the human [102]. The agent has budget for the number of queries. To learn efficiently within the
The work done AWS AI Labs.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

budget, it needs to elicit preferences from the most informative lists, which allows it to learn to rank all other lists. Our main contribution is an efficient algorithm for computing the distribution of the most informative lists.
Our work touches on many topics. Learning of reward models from human feedback is at the center of RLHF [62] and its recent popularity has led to major theory developments, including analyses of regret minimization in RLHF [16, 87, 90, 91, 61, 75J. These works propose and analyze adaptive algorithms that interact with the environment to learn highly-rewarding policies. Such policies are usually hard to deploy in practice because they may harm user experience due to over-exploration [22, 82]. Therefore. Zhu et al. [102] studied RLHF from ranking feedback in the offline setting with fixed dataset. We study how collect an informative dataset for offline learning rank with both absolute and ranking feedback. We approach this problem as an optimal design, methodology for computing optimal informmtioonggtthenin can be precomputed, which is one of their advantages. The main technical contribution of this work is a matrix generalization of the Senfer-Wolfooizz theorem [41], which allows us to formulate optimal designs for ranked lists and solve them efficiently. Optimal designs have become standard tool in exploration [45, 37, 38, 58, 33] and adaptive algorithms can be obtained by combining them with elimination. Therefore, optimal designs are natural stepping stone to other solutions.
policies [66, 24]. The policies are non-adaptive and thus
We make the following contributions:
1. We develop a novel approach for human preference elicitation. The key idea is to generalize the Kiefer- Wolfowitt theorem [41] to matrices (Section 3), which then allows us compute informatiiongatheriinn policies for ranked lists.
2. We propose an algorithm that uses an optimal design to collect absolute human feedback (Section 4.1,, where a human provides noisy feedback for each item in the queried list. A least-squares estimator then used to learn preference model. The resulting algorithm both computationally and statistically efficient. We bound its prediction error (Section 4.2) and ranking loss (Section 4.3), and show that both decrease with the sample size.
3. We propose an algorithm that uses an optimal design to collect ranking human feedback (Section 5.1), where a human ranks all items in the list according to their preferences. An estimator of Zhu et al. [102] is then used to learn a preference model. Our approach is both computationally and statistically efficient, and we bound its prediction error (Section 5.2) and ranking loss (Section 5.3). These results mimic the absolute feedback setting and show the generality of our framework.
4. We compare our algorithms to multiple baselines in several experiments. We observe that the algorithms achieve a lower ranking loss than the baselines.
2 Setting
Notation:
Let [K] (1, ..,,. KJ. Let A be the probability simplex over [L]. For any distribution π E A we get Σ T(i) = 1. Let (T2(K) k) [K]² j < k} be the set of all pairs over [K] where the first entry is lower than the second one. Let ||x| = x Ax for any positive-defintt A E IRd and x E Rd. We use Ô for the big-O notation up to logarithmic factors. Specifically, for any function f. we write (T)) if it is ((f(n) log* f((n) for some k > 0. Let supp (I)) be the support of distribution π or a random variable.
Setup: We learn to rank L lists, each with K items. An item & E [K] in list i E [L] is represented by feature vector X, E X, where X S Rd is the set of feature vectors. The relevance of items x,,,0... where O. E Rd is an
given by their mean rewards. The mean reward of item l in list unknown parameter. Without loss of generality, we assume that the original order of the items is optimal, 0, > x_x,0, O, for any j < k and list i. The agent does not know it. The agent interacts with humans for n rounds. At round t, it selects a list I, and the human provides stochastic feedback on it. Our goal is to design a policy for selecting the lists such that the agent learns the optimal order of all items in all lists after n rounds.
Feedback model: We study two models of human feedback, absolute and ranking:

---

(1) In the absolute feedback model, the human provides reward for each item in list I chosen by the agent. Specifically, the agent observes noisy rewards
Ut.k = 0 + 7t,k
(1)
for all & E [K] in list 4t where k is independent zero-mean SauuSsasi noise. This feedback is stochastic and similar to that in the document-bis based click model [19].
(2) In the ranking feedbuck model, the human orders all items in list J selected by the agent. The feedback is a permutation o2 [K] + [K], where or (k) is the index of the k-th ranked item. The probability that this permutation is generated is
K
exp[x] (R) 0.]
p(a,) = II
j= exple jx 0.]
Simply put, items with higher mean rewards are more preferred by humans and hence more likely to be ranked higher. This feedback model is known as the Plackett-Luce (PL) model [65, 54, 102], and it is standard assumption when learning values of individual choices from relative feedback. Since the feedback at round è is with independent noise, in both (1) and (2), any list can be observed multiple times and we do need to assume that n S L.
Objective: At the end of round n, the agent outputs a permutation 6,, [K] + [K] for all lists i [Z]. where (k) is the index of the k-th ranked item in list i. We measure the quality of the solution by the ranking loss after n rounds, which we define as
RA ΣΣΣ ((..())>@m.(k))) =-
The loss is the number of incorrectly ordered pairs of items in permutation Gn, summed over all lists i E [L.. can also be viewed as the Kendall tau rank distance [40] between the optimal order of items in all lists and that according to Gn,i. We note that other ranking metrics exist, such as the normalized discounted cumulative gain (NDCG) [86] and mean reciprocal rank (MRR) [85]. Our work can be extended to them and we leave this for future work.
The two closest related works are Mehta al. [56] and Das et al. [20]. They proposed algorithms for learning to rank L pairs of items from pairwise feedback. Their optimized metric is the maximum gap over the L pairs. We learn rank L lists of K items from K wwway ranking feedback. We bound the maximum prediction error, which is similar metric to the prior works, and the ranking loss in (3), which is novel. Our setting related to other bandit settings as follows. Due to the budget n, it is similar to fixed- fixed-budget best arm identification (BAI) [13, 5, 6, 95]. The main difference is that we do not want to identify the best arm. We want to sort L lists K items. Online learning to rank has also been studied extensively [67, 43, 105, 53, 44]. We do not minimize cumulative regret or try to identify the best arm. A more detailed comparison is Appendix
We introduce optimal designs [66, 24] next. This allows us to minimize the expected ranking loss within a budget of rounds efficiently.
3 Optimal Design and Matrix Kiefer- WolfowiZ
This section introduces a unified approach to human preference elicitation from both absolute and ranking feedback. First, we note that to learn the optimal order of items in all lists, the agent has to estimate the unknown model parameter 0,, well. In this work, the agent uses maximum waximum-llikllhood likelihood estimator (MLE) to obtain an estimate Ô,, of o.. After that, it orders the items in all lists according to their estimated mean rewards xT, A, in descending order, which defines the permutation o,,;- If Ó, minimized the prediction error (xT,, (Ô, - 0z))² over all items à E [K] in list i, the permutation on,; would closer to the optimal order. Moreover, if Ô., minimized the maximum error over all lists, all permutations would be closer and the ranking loss in (3) would be minimized. This is why we focus on minimizing the maximum prediction error
Σ A
(a T (Ó, - 0.))² max tr tr] (Ō.. - 0.)(O, - -O.) A.), [L[
max (E
3

---

where A, is a matrix representing list and a E A, is a column in it. In the absolute feedback model, the columns of A, are feature vectors of items in list i (Section 4.1). In the ranking feedback model, the columns of A; are the differences of feature vectors of items in list i (Section 5.1). Therefore, A; depends on the type of human feedhack. fact, as we show later, it dictated by the covariance of On in the corresponding human feedback model. We note that the objective in (4) worst-case over lists and that other alternatives, such as 1 E EaEA, (a (Ô.. - 0.))², may be possible. We leave this for future work.
We prove in Sections and that the agent can minimize the maximum prediction error in (4) and the ranking loss in (3) by sampling from fixed distribution n, E A That is, the probability of selecting list i at round is P (I+ = i) = n. (1). The distribution n, is a minimizer of
g max EE[T]
(5)
where V= V==EI A
a design matrix. The optimal design aims to find the distribution Ty. Since (5) does not depend the received feedback, our algorithms are not adaptive.
The problem of finding т, that minimizes (5) is called the G-optimal design [45]. The minimum of (5) and the support of т. are characterized by the theorem is for sausrss regression, where A, are feature vectors. At high level, it says that the smallest ellipsoid that covers all feature vectors has the minimum volume. and in this way relates the minimization of (5) to maximizing log det v+ We generalize this claim to lists, where A, is a matrix of feature vectors representing list i. This generalization allows to go from a design over feature vectors to a design over lists represented by matrices.
theorem [41, 45J. The original
Theorem (Matrix Kiefer-Wool Wolfowitz). Let M 2 be an integer and A A1,..., Ar, E RdxM be matrices whose column space spans Red Then the following claims are equivalent:
(a) na is a minimizer of ((T) in (5).
(b) πu is maximizer of f(T)) log x.)).
(c) g(T=) d.
Furthermore, there exists a minimizer T, of g(T) such that |supp (T.) S d(d + 11/2.
Proof. We generalize the proof of the Wolffortt theorem in Lattimore and Szepesvari [45]. The key observation is that even if A, is matrix and not vector, the design matrix V, is positive definite. Using this structure, we establish the key facts used in the original proof. First, we show that ff(=)= = (tr(A) V A.) is the gradient of f() with respect æ. In addition, we prove that V- As) = d. The complete proof is Appendix A.
g(T) 2 ΣL [.
From the equivalence in Theorem 1, it follows that the agent should solve the optimal design
T, arg max (TT) arg max log det(V=)
(6)
TEAL
#EA
and sample according to w. to minimize the maximum prediction error in (4). Note that the optimal design over lists (6) is different from the one over vectors [45]. As an example, suppose that we have 4 feature vectors (x, ]eja] and two lists: A (x1, and A₂ = (X3. x4). The list design is over 2 variables (lists) while the vector design is over 4 variables (vectors). The list design can also be viewed constrained vector design, where (x1, x²) and (x3, x1) are observed together with the same probability.
The optimization problem in (6) is convex and thus easy to solve. When the number of lists is large, the Frank- Wolfe algorithm [59, 32] can be used, which solves convex optimization problems with linear constraints as sequence of linear programs. We use CVXPY [21] to compute the optimal design. We report its computation time, as a function of the number of lists L, in Appendix E. The computation time scales roughly linearly with the number of lists L. In the following sections, we employ Theorem to bound the maximum prediction error and ranking loss for both absolute and ranking feedback.

---

Algorithm Dope for absolute feedback.
Algorithm Dope for ranking feedback.
1: for i 1, L do
1: for 1..... L do
2:
A; + keiK
2:
for (j.k) E (22(K) do
3: V Σ T A
3:
Wiijk f- Xi,j Xi
4: Te f- arg A log det(V
4:
A, + (.AAA(G))))))
5: for = ,...,, do
V - π (i)
6: Sample I T.
6: т. < arg max log dct(V,)
7: for k . K do
7: fort = I...=,...,,f1 do
Observe Vr in (1) 9: Compute 0, in (7)
8:
8: Sample 4, ~ n.
9: Observe d. in (2)
10: for i 1, 1,.... do
10: Compute 0, in (10)
Set (k) the index of the item with
11:
for i l......... L do
the k-th highest 0, list
12: Set (k) the index of the item with
the k-th highest O,, list
12: Output: Permutation on for all [L]
13:
Output: Permutation on, for all i [L]
4 Learning with Absolute Feedback
This section is organized as follows. In Section 4.1, we present algorithm for human preference elicitation under absolute feedback. We bound its prediction error in Section 4.2 and its ranking loss in Section 4.3.
4.1 Algorithm Dope
Our algorithm for absolute feedback is called D-optimal preference elicitation (Dope). It has four main parts. First, solve the optimal design in (6) get data logging policy The matrix for list i is A; = [x],]] E d where X, is the feature vector of item & in list i. Second, we collect human feedback for n rounds. At round E [n]. we sample a list ~ m, and then observe kt, for all k [K], as defined in (I). Third, we estimate the model parameter using least squares
K
0, =
kl,kk
(= k=1
The normalized and unnormalized covariance matrices corresponding to the estimate are
Σn - 2n Σ, 71
XI.,&L,, L.kk
(8)
respectively. Finally, the items in all lists according their estimated mean rewards x,, in descending order, obtain the permutation o,, The pseudo-code of Dope is in Algorithm
The estimator (7) is the same as ordinary least squares (OLS), because each observed list can be treated K independent observations. The matrix for list i, A,, be related to the inner sum in (8) through tr (r(A,A]) = K x Therefore, our algorithm collects data for a least-squares estimator by optimizing its covariance [45, 33).
4.2 Maximum Prediction Error Under Absolute Feedback
In this section, we bound the maximum prediction error of Dope under absolute feedback. We start with lemma that uses the optimal design π.. to bound max Eas ||al|
Lemma 2.
Let n, be the optimal design (6). Fix budget n and let each allocation ni, be an integer. Then max EnEA, || d/n.
The lemma is proved in Appendix A.2. Since all nı,, (i) are integers, we note that Σ,, must full rank and invertible. Note that the assumption of all no,, (1) being integers does not require > L.
5

---

This is because Tu (2) has at most d(d + 1)/2 non-zero entries (Theorem 1). This is independent of the number of lists L, which could also be infinite (Chapter 21.1 in Lattimore and Szepesvari [45]). The integer condition can be also relaxed by rounding non-zero entries of nı. (i) up to the closest integer. This clearly yields an integer allocation of size at most n. - d(d + 1)/2. All claims in our work would hold for any *, and this allocation. With Lemma 2 in hand, the maximum prediction error is bounded as follows.
Theorem 3 (Maximum prediction error). With probability at least 1 1- 8, the maximum prediction error after n. rounds is
(L + ( d
0.) max tr(A, (O.. 0.) 0.) A.) -.)) [
The theorem is proved in Appendix A.3. As Lemma 2. we assume that each allocation no. (i) is an integer. If the allocations
not integers, rounding errors would arise and need to be bounded [66, 25, 37]. At a high level, our bound would be multiplied by 1 + 3 for some > 0 (Chapter 21 in Lattimore and Szepesvari [45]). We omit this factor in our proofs simplify them.
Theorem 3 says that the maximum prediction error is (LP Note that this rate cannot be attained trivially, for instance by uniform sampling. To see this, consider the following example. Take K Let x, = (1, 0, 0) for E [L. 1] and X,, = (0, 1, 0), and x,,2 = (0, 0, 0) for all i E [Z]. In this case, the minimum eigenvalue of Σ, is n L in expectation, because only one item in list L provides information about the second feature, XL.1 = (0, 1, 0). Following the proof of Theorem 3, we would get a rate OdL/n)). Prior works on optimal designs also made similar observations [78].
The rate in Theorem 3 is the same as in linear models [45]. Specifically, by the Cauchy-Schward inequality, we would get
(x (0n, 0.)) S 00,
=((d) O(d)
with high probability, where 0., On, and E,, are the analogous linear model quantities. This bound holds for infinitely many feature vectors. It can be tightened to (dd/n) for finite number of feature vectors, where Ô hides the logarithm of the number of feature vectors. This can be proved using union bound over (20.3) in Chapter 20 of Lattimore and Szepesvari [45].
4.3 Ranking Loss Under Absolute Feedback
In this section, we bound the expected ranking loss under absolute feedback. Recall from Section 2 that the original order of items in each list optimal. With this in mind, the gap between the mean rewards of items j and i in list i is Dij, (Xx.) x4,x) O.. for any i E [L] and (j,k) E [I2.)). Theorem (Ranking loss). The expected ranking loss after n rounds is bounded as
K
A A
j
E[RM] 22
exp
8d
kmj+1
Proof. From the definition of the ranking loss, we have
K
E E
Σ Σ
B[1(on.()) Gn, Gn, (b))
Σ
Σ
P
PxxT,0x < <x]
kmj+1
kmj+1
where P 0x < xTT 0m.)
is the probability of predicting a sub-optimal item above item y in list
1. We bound this probability from above by bounding the sum of PP (xTTx (0. 0.) > A.j..
and
2
P x (0. 0.)) A... Each of these probabilities is bounded from above by exp
A
8d
using a concentration inequality in Lemma 8. The full proof is in Appendix A.4.
42
Each term in Theorem 4 can be bounded from above by exp d is the number of features, and Amin denotes the minimum gap. Therefore, the bound decreases
min 8d
where is the sample size,

---

exponentially with budget and gaps, and increases with d. This dependence is similar to that in Theorem of Azizi al. [6] for fixed-budget best-arm identification linear models. Yang and Tan [95] derived a similar bound and a matching lower bound. The gaps Aij.k reflect the hardness of sorting list i, which depends on the differences of the mean rewards of items j and l: in
Finally, we wanted to note that our optimal designs may not be optimal for ranking. We have not focused solely on ranking because we see value in both prediction error (Theorem and ranking loss (Theorem 4) bounds. The fact that we provide both shows the versatility of our approach.
5 Learning with Ranking Feedback
This section is organized similarly to Section 4. In Section 5.1, present algorithm for human preference elicitation under ranking feedback. We bound its prediction error in Section 5.2 and its ranking loss in Section 5.3. Our algorithm design and analysis are under the following assumption, which we borrow from Zhu et al. [102].
Assumption 1. We assume that the model parameter satisfies 0, E O, where
θ (0 R 0 0, ||0 s
We also assume that [[ X < 1.
The assumption of bounded model parameter and feature vectors is common in bandits [1, 45]. The additional assumption of 1a = is from Zhu et al. [102], from which we borrow the estimator
and concentration bound.
5.1 Algorithm Dope
Our algorithm for ranking feedback is similar to Dope in Section 4. It also has four main parts. First, we solve the optimal design problem in (6) to obtain a data logging policy Te- The matrix for list 1)/2, where Zi.j. = X; - x,, is the difference of feature vectors of items j and l in list Second, collect human feedback for rounds. At round [n]. we sample list Ię π. and then observe drawn from the PL model, as defined in (2). Third, we estimate the model parameter
A, [z..j.k j ())T)))) E
K
exp X (k)
0
0, = arg min (0), (0)
log
(10)
jj=k expl x T1
where is defined in Assumption 1. We solve this estimation problem using iteratively reweighted least squares (IRLS) [89], popular method for fitting the parameters of generalized linear models (GLMs). Finally, sort the items in all lists according to their estimated mean rewards x. in descending order, to obtain the permutation ,, The pscudo-code of Dope is in Algorithm 2.
The optimal design for (10) is derived as follows. First, we derive the Hessian é,, (0), (,,,(0) in Lemma 9. The optimal design with 2 (6) cannot be solved exactly because 2, depends on an unknown model parameter 0. To get around this, we bound O-dependent terms from below. Many prior works on decision making under uncertainty with GLMs [26, 52, 102, 20, 99] took similar approach. We derive normalized and unnormalized covariance matrices
2
Σn K(K 1)m Σn,
Σ,
Zt 21.
(11)
j=1k=
and prove that (0), 2 E,, for some 7 > Therefore, we can maximize log (eeet((V(, for any 0 E O, by maximizing log (En). The matrix for list A., can be related to the inner sum in (11) through tr(A:AT) Σx -K
Σkmj+h Z...A
The price to pay for our approximation is constant C > 0 in our bounds (Theorems 5 and 6). In Appendix C, we discuss more adaptive design and also compare to it empirically. We conclude that
it would be harder to implement and analyze, and we do not observe empirical benefits at K 2.
7

---

5.2 Maximum Prediction Error Under Ranking Feedback
In this section, we bound the maximum prediction error Dope under ranking feedback. Similarly to the proof of Theorem 3, we decompose the enror into two parts, which capture the efficiency of the optimal design and the uncertainty in the MLE 0n.
Theorem (Maximum prediction error). With probability at least - ô, the maximum prediction error after rounds is
max tr ( (0n. - (.) - -.) A.) = [ + dllog(1/8))
1E[L
This theorem is proved in Appendix A.5. We build on a self-normalizing bound of Zhu et al. [102], which may not be tight in K. If the bound could be improved by multiplicative c O. we would get multiplicative improvement in Theorem 5. Note that if the allocations ruTr, (i) are not integers, a rounding procedure necessary [66, 25, 37J. This would result in an additional multiplicative + / in our bound, for some B > O. We omit this factor in our derivations to simplify them.
||O,, 1-112,, So
K (dd+oog(1/81)
n
5.3 Ranking Loss Under Ranking Feedback
In this section, we bound the expected ranking loss under ranking feedback. Similarly to Section 4.3, we define the gap between the mean rewards of items and & in list as A i. O., where Ziiik Xi, 10-x,, X the difference of feature vectors of items j and k in list Theorem (Ranking loss). The expected ranking loss after rounds is bounded as
Ai.j.' CK4d +
EJRJ
exp
k=j+1
where C' is a constant.
Proof. The proof is similar to Theorem 4. At the end of round n, we bound the probability that
sub-optimal item is ranked above item j. The proof has two parts. First, for any list [L] and
items (j, k) (K), show that IP [x < 0x
P T (0. Q.)) A (..k)) Then
A a Ck'd + d The full proof is in Appendix A.6.
we bound this quantity by exp
The bound Theorem 6 is similar to that in Theorem 4, with the exception of multiplicative K-4 and additive d. The leading term inside the sum be bounded by exp
2 where is the C
sample size, d is the number of features, and Amin is the minimum gap. Therefore, similarly to Theorem 4, the bound decreases exponentially with budget n and gaps, and increases with This dependence is similar to Theorem 2 of Azizi et al. [6] for fixed-budget best-arm identification in GLMs. Our bound does not involve the extra factor of k. > 0 because we assume that all vectors lie in unit ball (Assumption l).
6 Experiments
The goal of our experiments is to evaluate Dope empirically and compare baselines. All methods estimate Ó, using (7) or (10), depending on the feedback. To guarantee that these problems are well defined, even if the sample covariance matrix Σn not full rank, regularize both objectives with 7 for a small > 0. This mostly impacts small sample sizes. Specifically, since the optimal design collects diverse feature vectors, Σ,, is likely to be full rank for large sample sizes. After θ,, is estimated, each method ranks items in all lists based their estimated mean rewards xT,, e,. The performance of all methods is measured by their ranking loss in (3) divided by L. All experiments are averaged over 100 independent runs, and we report results Figure I. We compare the following algorithms:

---

2.5
2.0
1.8
Unif
Dope (Ours)
Dope (Ours)
1.6
Aug Design
Avg Design
Ranking loss
Clustered Design
1.4
Clustered Design
APO
1.2
APO
1.5
1.0
0.8
0.6
0.5
10
20
30
40
60
70
80
90
100
16
20
30
40
50
60
70
80
90
100
Number logged interactions
Number of lagged interactions
(a) Absolute feedback
(b) Ranking feedback
2.0
0.40
Unif
Dape (Ours)
0.35
Dope (Ours)
1.5
Avg Design
Avg Design
Banking loss
Ranking loss
0.30
Clusstrrdd Design
1.0
0.25
0.20
0.5
0.15
0.0
0.10
150
300 400
100
200 300 600 800 900 Number of logged interactions
Number of logged interactions
(c) Nectar dataset
(d) Anthropic dataset
Figure 1: Ranking loss of all compared methods as a function of the number of rounds. The error bars standard error of the estimates.
(1) Dope: This is our method. We solve the optimal design problem in (6) and then sample lists I according π.
(2) Unif: This baseline chooses lists I uniformly at random from [L]. While simple, is known to be competitive in real-world problems where feature vectors may cover the feature space close to uniformly [4, 96, 3, 70].
(3) Avg-Design: The exploration policy is an optimal design over feature vectors. The feature vector of list is the mean of the feature vectors of all items in it, x, * Σk X1,A- After the design is computed, we sample lists I according to it. The rest is the same as in Dope. This baseline shows that our list representation with multiple feature vectors can outperform more naive choices.
(4) Clustered Design: This approach uses the same representation as Avg-Design. The difference is that we cluster the lists using k-meeoids. Then we sample lists I, uniformly random from the cluster centroids. The rest the same as in Avg-Design. This baseline shows that Dope outperforms other notions of diversity, such as obtained by clustering. We tune & (k: 10 in the Nectar dataset and k 6 otherwise) and report only the best results.
(5) APO: This method was proposed in Das et al. [20] and is the closest related work. APO greedily minimizes the maximum error in pairwise ranking of L lists of length
We extend K as follows. First, we L lists of length K into (K) L lists of length one for each pair of items in the original lists. Then we apply APO to these (k) T. lists of length 2.
Pure exploration algorithms are often compared to cumulative regret baselines [13, 5]. Since
problem is a form of learning to rank, online learning to rank (OLTR) baselines [67, 43, 105] seem natural. We do not compare to them for the following reason. The problem of an optimal design over lists is to design distribution over queries. All OLTR algorithms solve a different problem, return a ranked list of items conditioned queries, they cannot solve our problem.
query chosen by the environment. Since they do not choose the
Synthetic experiment (absolute feedback): We have I. = 400 questions and represent them by random vectors q: E [-1, 1]6, Each question has K answers. each question, we generate K random answers a E [ 1j. Both the question and answer vectors normalized to unit length.

---

For each question-anssee answer pair ki, the feature vector is X = vec(qqa and has length d = 36. The outer product captures cross-interaction terms of the question and answer representations. A similar technique has been used for feature preprocessing of the Yahoo! Front Page Today Module User Click Log Dataset [50, 51, 103, 7]. We choose a random 0, E [0, __ The absolute feedback is generated as in (I). Our results are reported in Figure ((a). We note that the ranking loss of Dope decreases the fastest among all methods, with Unif, Avg-Design and APO being close second.
Synthetic experiment 2 (ranking feedback): This experiment is similar to the first experiment, except that the feedback is generated by the PL model in (2). Our results are reported in Figure 1(b) and we observe again that the ranking loss of Dope decreases the fastest. The closest baselines Unif, Avg- ggg-eigg,, and APO. Their lowest ranking loss (n = 100) is attained by Dope at n = 60, which is nearly two-fold reduction in sample size. In Appendix E, we conduct additional studies on this problem. We vary the number of lists L and items K, and report the computation time and ranking loss.
Experiment 3 (Nectar dataset): The Nectar dataset [101] is a dataset of 183k questions, each with 7 answers. We take a subset of this dataset: L = 2 200 questions and K 5 answers. The answers generated by GPT-4, GPT-4-0613, GPT-3.5-turbe. We embed the questions and answers in 768 dimensions using Instructor embeddings [79]. Then we project them to R210 using a random projection matrix. The feature vector of answer k to question i is X = veo(q.a..,) ) where qi and a,,k the projected embeddings of question i and answer k, respectively. Hence d = 100. The ranking feedback is simulated using the PL model in (2). We estimate its parameter 0. E Rd from the ranking feedback in the dataset using the MLE in (10). Our results are reported in Figure ((c). We observe that the ranking loss of Dope is the lowest. The closest baseline is APO. Its lowest ranking loss (n = 500) is attained by Dope at n = 150, which is more than three-fold reduction in sample size.
GPT-3.5-turbo-instruuct, and Anthropic models.
The Anthropic dataset [8] is a dataset of 161k questions with two answers per question. We take subset of L 2 000 questions. We embed the questions and answers in 768 dimensions using Instructor embeddings [79]. Then we project them to IR using a random projection matrix. The feature vector of answer & to question i is X,, vec(q.a...) where qi and a,, are the projected embeddings of question and answer k. respectively. Hence d = 36. The ranking feedback is simulated using the PI. model in (2). We estimate its parameter 0, R from the feedback in the dataset using the MILE in (10). Our results are reported in Figure 1(d). We note again that the ranking loss of Dope is the lowest. The closest baselines are Unif, Syg-Design, and APO, Their lowest ranking loss (n = 1 (00) is attained by Dope at n = 300, which is more than a three-fold reduction in sample size.
Experiment (Anthropic dataset):
7 Conclusions
We study the problem of optimal human preference elicitation for learning preference models. The problem is formalized as learning to rank K answers to L questions under a budget on the number of asked questions. We consider two feedback models: absolute and ranking. The absolute feedback is motivated by how humans assign relevance judgments in search [30, 57]. The ranking feedback is motivated by learning reward models RLHF [39, 68, 36, 15, 77, 17]. We address both settings in unified way. The key idea in our work is to generalize optimal designs [41, 45], methodology for computing optimal information- -gattring policies, to ranked lists. After the human feedback is collected, we learn preference models using existing estimators. Our method is statistically efficient, computationally efficient, and can be analyzed. We bound its prediction errors and ranking losses, in both absolute and ranking feedback models, and evaluate it empirically to show that it is practical.
Our work can be extended in several directions. First, we study only two models of human feedback: absolute and ranking. However, many feedback models exist [34]. One common property of these models that learning of human preferences can be formulated as likelihood maximization, In such cases, an optimal design exists and can be used for human preference elicitation, exactly as in our work. Second, while we bound the prediction errors and ranking losses of Dope, we do not derive matching lower bounds. Therefore, although we believe that Dope is near optimal, we do not prove it. Third, we want to extend our methodology to the fixed-confidence setting. Finally, we want to apply our approach to learning reward models in LLMs and evaluate it.
10

---

References
[1] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Riad Akrour, Marc Schoenauer, and Michèle Sebag. April: Active preference learning- based reinforcement learning. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2012, Bristol, UK, September 24-28, 2012, Proceedings, Part 1I 23, pages 116-131. Springer, 2012.
[3] Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Sham Kakade. Gone fishing: Neural active learning with fisher embeddings. Advances in Neural Information Processing Systems, 34, 2021.
[4] Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. arXiv preprint arXiv:1906. 03671,2011
[5] Jvan-Yves Audibert, Sebastien Bubeck, and Remi Munos. Best arm identification in multi- armed bandits. In Proceedings of the 23rd Annual Conference on Learning Theory, pages
41-53, 2010.
[6] Mohammad Javad Azizi, Branislav Kveton, and Mohammad Ghavamzadeh. Fixed-budget best-arm identification in structured bandits. In Proceedings of the 31st International Joint Conference on Artificial Intelligence, 2022.
[7] Jackie Baek and Vivek Farias. Ts-ucb: Improving thompson sampling with little to additional computation. In International Conference on Artificial Intelligence and Statistics, pages 11111111111 148. PMLR, 2023.
[8] Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.0580 055622. 2022.
[9] Viktor Bengs, Róbert Busa-Fekete, Adil EI Mesaoudi-Paul and Eyke Hüllermeier. Preference- based online learning with dueling bandits: survey. The Journal of Machine Learning Research,
2021.
[10] Erdem Bıyık, Nicolas Huynh, Mykel J Kochenderfer, and Dorsa Sadigh. Active preference- based gaussian process regression for reward learning. arXiv preprint arXiv:2005.0233 02575, 2020.
[11] Stephane Boucheron, Gabor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013.
[12] Ralph Allan Bradley and Milton Terry. Rank analysis of incomplete block designs: the method of paired comparisons. Biometrika, 39(3-4):3243445, 1952.
[13] Sebastien Bubeck, Remi Munos, and Gilles Stoltz. Pure exploration in multi armed bandits problems. In Proceedings of the 20th International Conference on Algorithmic Learning Theory, pages 23-37, 2009.
[14] Christopher Burges. From RankNet LambdaRank to LambdaMART: An overview. Technical Report MSR-TTR-2000-82, Microsoft Research, 2010.
[15] Stephen Casper, Xander Davies, Claudia Shi, Thomas Krendl Gilbert, Jérémy Scheurer, Javier Rando, Rachel Freedman, Tomasz Korbak, David Lindner, Pedro Freire, et al. Open problems and fundamental limitations of reinforcement learning from human feedback. arXiv preprint arXiv:2307.1 152.37...5111.... 2023.
[16] Xiaoyu Chen, Han Zhong, Zhuoran Yang. Zhaoran Wang. and Liwei Wang. Human-in- the- Provably efficient preference- based reinforcement learning with general function approximation. In International Conference on Machine Learning, pages 3773-3793. PMLR, 2022.
[17] Zhuotong Chen, Yifei Ma, Branislav Kveton, and Anoop Deoras. Active learning with crowd sourcing improves information retrieval. In ICML. 2023 Workshop on Interactive Learning with Implicit Human Feedback, 2023.

---

[18] Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
[19] Aleksandr Chuklin, llya Markov, and Maarten De Rijke. Click models for web search. Springer Nature, 2022.
[20] Nirjhar Das, Souradip Chakraborty, Aldo Pacchiano, and Sayak Ray Chowdhury. Active preference optimization for sample efficient RLHF. CoRR, Abs/2402.10500, 2024. URL https//arriv.or//as2220...00 10500.
[21] Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 1 17(83):1-5, 2016.
[22] Miroslav Dudik, Dumitru Erhan, John Langford, and Lihong Li. Doubly robust policy evaluation and optimization. Statistical Science, 29(4):485-511, 2014.
[23] Beyza Ermis, Patrick Ersst Yannik Stein, and Giovanni Zappella. Learning to rank in the position based model with bandit feedback. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 2405-2411 2020.
[24] Valerii Vadimovich Fedorov. Theory of optimal experiments. Elsevier, 2013.
[25] Tanner Fiez, Lalit Jain, Kevin G Jamieson, and Lillian Ratliff. Sequential experimental design for transductive linear bandits. Advances neural information processing systems, 32, 2019.
[26] Sarah Filippi, Olivier Cappe, Aurelien Garivier, and Csaba Szepesvari. Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems 23, pages 586-594, 2010.
[27] Johannes Fürnkranz and Eyke Hüllermeier. Pairwise preference learning and ranking. In European conference machine learning, pages 145-156. Springer, 2003.
[28] Alyssa Glass. Explaining preference learning, 2006.
[29] Joey Hejna and Dorsa Sadigh. Inverse preference learning: Preference-basee based rl without reward function. arXiv preprint arXiv:2305. 15363, 2023.
[30] Katja Hofmann, Shimon Whiteson, and Maarten de Rijke. Fidelity, soundness, and efficiency of interleaved comparison methods. ACM Transactions on Information Systems, 31(4):1-43, 2013.
[31] Neil Houlsby, Ferene Huszár, Zoubin Ghahramani. and Máté Lengyel. Bayesian active learning for classification and preference learning. arXiv preprint arXiv: 2011.
[32] Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In Interna- tional conference machine learning, pages 427-435. PMLR, 2013.
[33] Kevin Jamieson and Lalit Jain. Interactive machine learning. 2022.
[34] Hong Jun Jeon, Smitha Milli, and Anca Dragan. Reward-rational (implicit) choice: A unifying formalism for reward learning. In Advances in Neural Information Processing Systems 33, 2020.
[35] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline ri? In International Conference on Machine Learning, pages 5084-5096. PMLR, 2021.
[36] Yachen Kang, Diyuan Shi, Jinxin Liu, Li He, and Donglin Wang. Beyond reward: Offline preference-guided policy optimization, 2023.
[37] Julian Katz-Samuels, Lalit Jain, Kevin G Jamieson, al. An empirical process approach the union bound: Practical algorithms for combinatorial and linear bandits. Advances in Neural Information Processing Systems, 33: 33:10371-10382 2020.
[38] Julian Katz Satz-Samuels, Jifan Zhang, Lalit Jain, and Kevin Jamieson. Improved algorithms for agnostic pool-based active classification. In International Conference on Machine Learning. pages 5334-5344, PMLR, 2021.
[39] Timo Kaufmann, Paul Weng, Viktor Bengs, and Eyke Hüllermeier. A survey of reinforcement learning from human feedback, 2024.
[40] Maurice George Kendall. Rank correlation methods. 1948.
12

---

[41] Jack Kiefer and Jacob Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960.
[42] Johannes Kirschner and Andreas Krause. Bias-robust Bayesian optimization via ducling bandits. In Proceedings of the 38th International Conference on Machine Learning, 2021.
[43] Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan. Cascading bandits: Learning to rank in the cascade model. In Proceedings of the 32nd International Conference on Machine Learning, 2015.
[44] Paul Lagree, Claire Vernade, and Olivier Cappe. Multiple-play bandits the position-based model. In Advances in Neural Information Processing Systems 29, pages 1597-1605, 2016.
[45] Tor Lattimore and Csaba Szepesvari. Bandit Algorithms. Cambridge University Press, 2019.
[46] Tor Lattimore, Branislav Kveton, Shuai Li, and Csaba Szepesvari. TopRank: A practical algorithm for online stochastic ranking. In Advances in Neural Information Processing Systems 31, pages 3949-3958, 2018.
[47] Kimin Lee, Laura Smith, Anca Dragan, and Pieter Abbeel. B-pref: Benchmarking preference- based reinforcement learning. arXiv preprint arXiv:2111.03006 2021.
[48] Tyler Lekang and Andrew Lamperski. Simple algorithms for dueling bandits. arXiv preprint arXiv:1906. (tti::/990.00611,, 1, 2019.
[49] John R Lepird, Michael P Owen, and Mykel Kochenderfer. Bayesian preference elicitation for multiobjective engineering design optimization. Journal of A'Arroppcce Information Systems, 12(10):634-445, 2015.
[50] Lihong Li, Wei Chu, John Langford, and Robert Schapire. contextual-bandi approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[51] Lihong Li, Wei Chu, John Langford, and Xuanhui Wang. Unbiased offline evaluation of sitextuul-bandit-baaeee news article recommendation algorithms. In Proceedings of the fourth ACM international conference on Web search and data mining, pages 297-306, 2011.
[52] Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In Proceedings of the 34th International Conference on Machine Learning. pages 2071-2080 2017.
[53] Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual combinatorial cascading bandits. In Proceedings of the 33rd International Conference on Machine Learning, pages 1245-1253, 2016.
[54] Robert Dunean Luce. Individual Choice Behavior: Theoretical Analysis. Dover Publications, 2005.
[55] Blake Mason, Kwang-Sung Jun, and Lalit Jain, An experimental design approach for re- gret minimization in logistic bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
[56] Viraj Mehta, Vikramjeet Das, Ojash Neopane, Yijia Dai, Ilija Bogumovic, Jeff Schneider, and Willie Neiswanger. Sample efficient reinforcement learning from human feedback via active exploration. CORR, abs/2312.000 2.00267, 2023. URL httpss//arivvorr//b/3331.1.00000
[57] MS MARCO. MS MARCO Dataset. https:/microooftt http://ot.giiiuubbbbooormoooooo 2016.
[58] Subhojyoti Mukherjee, Ardhendu S Tripathy, and Robert Nowak. Chernoff sampling for active testing and extension to active regression. In International Conference on Artificial Intelligence and Statistics, pages 7384-7432. PMLR, 2022.
[59] Jorge Nocedal and Stephen Wright. Numerical optimization. Springer, 1999.
[60] Ellen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick. Dueling posterior sampling for preference-based reinforcement learning. In Conference on Uncertainty in Artificial Intelligence, pages 1029-1038. PMLR, 2020.
[61] Kweku Opoku- Agyemang. Randomized controlled trials via reinforcement learning from human feedback. 2023.
13

---

[62] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang. Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730-27744, 2022.
[63] Barna Pasztor, Parnian Kassraie, and Andreas Krause. Bandits with preference feedback: A stackelherg game perspective. CoRR, abs/2406.167455 2024. URL httphps//aannivoog//b////400 16745.
[64] Kaare Petersen and Michael Pedersen. The matrix cookbook. http://wwww2.compitee..uuu pubdh/pubs/3274- futllluuubb/2744fllhh.mmm, 2012.
[65] Robin Lewis Plackett. The analysis of permutations. Journal of the Royal Statistical Society: Series C (Applied Statistics, 24(2):193-202 1975.
[66] Friedrich Pukelsheim. Optimal Design of Experiments. Society for Industrial and Applied Mathematics, 2006.
[67] Filip Radlinski, Robert Kleinberg, and Thorsten Joachims. Learning diverse rankings with multi-armed bandits. In Proceedings of the 25th International Conference on Machine Learn- ing, pages 784-791, 2008.
[68] Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly reward model. In Seirty-seventh Conference on Neural Information Processing Systems, 2023. URL
[69] Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell, Bridging offline reinforcement learning and imitation learning: tale of pessimism. Advances in Neural Information Processing Systems, 34:1 1702-11716. 2021.
[70] Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Yao Huang, Zhihui Li, Brij B Gupta, Xiaojiang Chen, and Xin Wang. A survey of deep active learning, ACM Computing Surveys (CSUR), 54 19):1-40, 2021.
[71] Dorsa Sadigh, Anca Dragan, Shankar Sastry, and Sanjit Seshia. Active preference-based learning of reward functioon. 2017.
[72] Aadirupa Saha. Optimal algorithms for stochastic contextual preference bandits. In Advances in Neural Information Processing Systems 34, 2021.
[73] Aadirupa Saha and Pierre Gaillard. Versatile dueling bandits: sest-of-both-worde analyses for online learning from preferences. arXiv preprint arXiv:2202 06694, 2022.
[74] Aadirupa Saha and Akshay Krishnamurthy. Efficient and optimal algorithms for contextual dueling bandits under realizability. In Proceedings of the 33rd International Conference on Algorithmic Learning Theory, 2022.
[75] Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee. Dueling rl: Reinforcement learning with trajectory preferences. In International Conference on Artificial Intelligence and Statistics, pages 6263-6289. PMLR, 2023.
[76] Ayush Sekhari, Karthik Sridharan, Wen Sun, and Runzhe Wu, Contextual bandits and imitation learning with preference-based active queries. Advances in Neural Information Processing Systems, 36, 2024.
[77] Tianhao Shen, Renren Jin, Yufei Huang, Chuang Liu, Weilong Dong, Zishan Guo, Xinwei Wu, Yan Liu, and Deyi Xiong. Large language model alignment: A survey. arXiv preprint arXiv:2309. 5025, 2023.
[78] Marta Soare, Alessandro Lazaric, and Remi Munos. Best-arm identification in linear bandits.
In Advances in Neural Information Processing Systems 27, pages 828-836, 2014.
[79] Hongjin Su, Weijia Shi, Jungo Kasai, Yizhong Wang, Yushi Hu, Mari Ostendorf, Wen-tau Yih, Noah A. Smith, Luke Zettlemoyer, and Tao Yu. One embedder, any task: Instruction-finette finntuned text embeddings. 2022. URL https//ariv.or//bb//112.../
[80] Yanan Sui, Masrour Zoghi, Katja Hofmann, and Yisong Yue. Advancements in dueling bandits.
In IJCAL, pages 5502-5510, 2018
[81] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press,
2018.
14

---

[82] Adith Swaminathan and Thorsten Joachims. Counterfactual risk minimization: Learning from logged bandit feedback. In Proceedings of the 32nd International Conference on Machine Learning, pages 814-823, 2015.
[83] Balázs Szörényi, Róbert Busa-Fekete, Adil Paul, and Eyke Hüllermeier. Online rank elicitation for plackett-luce: A dueling bandits approach. Advances in neural information processing systems, 28, 2015.
[84] Shion Takeno, Masahiro Nomura, and Masayuki Karasuyama. Towards practical preferential Bayesian optimization with skew Gaussian processes. In Proceedings of the 40th International Conference on Machine Learning, 2023.
[85] EM Voorhees. Proceedings of the 8th text retrieval conference. TREC-8 Question Answering Track Report, pages 77-82, 1999.
[86] Yining Wang. Liwei Wang. Yuanzhi Li, Di He, and Tie- Yan Liu. A theoretical analysis of ndeg type ranking measures. In Conference on learming theory, pages 25-54. PMLR, 2013.
[87] Yuanhao Wang. Qinghua Liu, and Chi Jin. Is rlhf more difficult than standard r!? a theoretical perspective. In Shirtt--eventh Conference Neural Information Processing Systems, 2023.
[88] Christian Wirth, Riad Akrour, Gerhard Neumann, Johannes Fürnkranz, et al. A survey of preference-basee based reinforcement learning methods. Journal of Machine Learning Research, 18 (136):1-46, 2017.
[89] R. Wolke and H. Schwetlick. Iteratively reweighted least squares: Algorithms, convergence analysis, and numerical comparisons. SIAM Journal on Scientific and Statistical Computing, 9 (5):077-221, 1988.
[90] Runzhe Wu and Wen Sun. Making rl with preference-based feedback efficient via randomiza- tion. arXiv preprint arXiv:2310. 14554, 2023.
[91] Wei Xiong, Hanze Dong, Chenlu Ye, Han Zhong, Nan Jiang, and Tong Zhang. Gibbs sampling from human feedback: A provable kl-constrained framework for rlhf. arXiv preprint arXiv:2312. /1456, 2023.
[92] Wenjie Xu, Wenbin Wang, Yuning Jiang, Bratislav Svetozarevie, and Colin Jones. Principled preferential Bayesian optimization. In Proceedings of the 41th International Conference on Machine Learning, 2024.
[93] Yichong Xu, Aparna Joshi, Aarti Singh, and Artur Dubrawski. Zeroth order non-convex opti- mization with dueling-choice bandits. In Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence, 2020.
[94] Yichong Xu, Ruosong Wang, Lin Yang, Aarti Singh, and Artur Dubrawski. Preference-based reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33:18784-18799 18794, 2020.
[95] Junwen Yang and Vincent Tan. Minimax optimal fixed-budget best arm identification in linear bandits. In Advances in Neural Information Processing Systems 35, 2022.
[96] Michelle Yuan, Hsuan-Tien Lin, and Jordan Boyd-Graber. Cold-start active learning through self-supervised language modeling. arXiv preprint arXiv:2010.09535,, 2020.
[97] Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 7855)1153-11566 2012.
[98] Andrea Zanette, Martin J Wainwright, and Emma Brunskill. Provable benefits of actor-critii methods for offline reinforcement learning. Advances in neural information processing systems, 34: 14:13622 0e211366613666 13640, 2021.
[99] Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason Lee. Provable reword-agnostic preference-basee reinforcement learning. In Proceedings of the 12th International Conference on Learning Representations, 2024.
[100] Tianchen Zhou, Jia Liu, Yang Jiao, Chaosheng Dong, Yetian Chen, Yan Gao, and Yi Sun. Bandit learning to rank with bosted click models: Personalized and equal treatments. arXiv preprint arXiv:2311.04522 2023.
[101] Banghua Zhu, Evan Frick, Tianhao Wu, Hanlin Zhu, and Jiantao Jiao. Starling- Improving Il helpfulness & harmlessness with rlaif, November 2023.
15

---

[102] Banghua Zhu, Jiantao Jiao, and Michael Jordan. Principled reinforcement learning with human feedback from pairwise or K K-wise comparisons. CoRR, abs/2301. 2023. URL
https://axiv..rraas//20..1111 1270..
[103] Yinglun Zhu, Dongruo Zhou, Ruoxi Jiang, Quanquan Gu, Rebecca Willett, and Robert Nowak. Pure exploration in kernel and neural bandits. Advances in neural information processing systems, 34:1 111--16600 2021.
[104] Masrour Zoghi, Tomas Tunys, Mohammad Ghavamzadeh, Branislav Kveton, Csaba Szepesvari, and Zheng Wen. Online learning rank in stochastic click models. In Proceedings of the 34th International Conference on Machine Learning, 2017.
[105] Shi Zong, Hao Ni, Kenny Sung. Nan Rosemary Ke, Zheng Wen, and Branislav Kveton. Cascading bandits for large-scale recommendation problems. In Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, 2016
16

---

A Proofs
This section contains proofs of our main claims.
A.1 Proof of Theorem
We follow the sketch of the proof in Section 21. of Lattimore and Szepesvari [45] and adapt it to matrices. Before start, prove several helpful claims.
First, using (43) in Petersen and Pedersen [64], we have
θπ((1) ((T)
(i) log det v+) = tr V
V
a (i)
In the last step. we use the cyclic property the trace. We define the gradient of f(x)) with respect to Vf(²) (tr(A) V 2 Second, using basic properties of the trace, we have
Σ (
Σ 7(1) tV A,A,) tr Σ + ((VEE'AAT)
(12)
((AAT -tr(La)=
- =d.
Finally, for any distribution n, (12) implies
( max (A V A,)
I =d.
(13)
L
Now we are ready to start the proof.
(b) (a): Let be maximizer of f(x). By first-order optimality conditions, for any distribution
π, we have
L Σ (1) (A)
0 (Vf(T)), a- T.) Σ (()
=Σ x()
In the last step, we use (12). Since this inequality holds for any distribution म, including Dirac at i for any E [L], have d 2 max (r(A, V=, g(x.). Finally, by (13), g(x) holds for any distribution Therefore, must be minimizer of g(T) and g(T.) d.
(c) = (b): Note that
[T.) R
n.) Σ (0)A( d max tr V d d=g(TT))
V-
iE(L]
holds for any distributions and т.. Since g(T,) = d, we have (V ). π - S 0. Therefore, by first-order optimality conditions, π. a maximizer of f(r)..
(a) + (c): This follows from the same argument as in (b) = (a). In particular, any maximizer n, of f(T) is minimizer of ( and g(T.) = d.
To prove that |supp (T.) S d(d + 1) 1)/2, we argue that T. can be substituted for a distribution with a lower support whenever |supp (T.)) d(d + 1)/2. The claim then follows by induction.
Let supp (T.) and suppose that |S] > d(d 1)/2. We start with designing suitable family of optimal solutions. Since the space of d x d symmetric matrices has d(d + 1)/2 dimensions, there must exist an L-dimensional vector 7) such that supp (17 S and
Σ A. = Og.d iES
(14)
17

---

where OU, is a d x d zero matrix. Let Te Tx + tr fort 2 0. An important property of x is that
log det(( log det V.. + (aEE(iAA)))
log det +V..).
EE
Therefore, any ne is optimal solution. However, may be distribution.
We prove that Te E A", for some > O, as follows. First, note that tr (r(A, m. A,) = holds for all i S. Otherwise nu could be improved. Using this observation, we have
Σ XES
n(1)
Σ iES
n()) tr V = Σ n()) [[V
RES
V EV.:Z(())))
7()AAAA =0,
tr
SES
where the last equality follows from (14). This implies that Eies 17(1) = and that n. E A for as long as πy Oz.
Finally, we take the largest feasible f, r = max(t > 0::mg A) and note that :T, has at least one more non-zero entry than n. while having the same value. This concludes the proof.
A.2
Proof of Lemma
We note that for any list E [L],
K
-1
Σ
|al| Σ
=
(r(A,
Σ
A.) = ir A
Σ
Xlc,
A,
acA;
Amm
A=
K
tr A
Ta
Xi,xX d
A
=
The third equality holds because all nu,, (i) are integers and n >> O. this case, the optimal design is exact and Σ, invertible, because all of its eigenvalues are positive. Now the definition of g(T,), apply Theorem 1, and get that
max tr A.) g(T.) d.
This concludes the proof.
A.3 Proof of Theorem 3
For any list E [Z., we have
tr(A, (0,, (O, 0.)
Σ (a (O,, -0,))² Σ (a Σ 1 ///2 10. 02))
A,
aeA;
Σ
||a|2 En 11 -0.11 0.11
A
where the last step follows from the Cauchy-Schine Schwarz inequality. Therefore,
max trA, (0,, - 0.)(0, 0.) O.)TT.)) TA) S max Σ
|a|| E.. 1 0,11
#E[L]
(E(L)
AEA;
max
|
E. n 1 0, 1
(
ac A.
Part II
Part
where we use Σn, nEE in the last step.
18

---

Part I captures the efficiency of data collection and depends on the optimal design. By Lemma 2,
|al Σ. -
IIRX
acA.
Part II measures how the estimated model parameter 6,, differs from the true model parameter 0.. under the empirical covariance matrix En. To bound this term, we use Lemma and get that
16d + 8log(1/6)
|0, 0.1 I
holds with probability at least 1 - 6. The main claim follows from combining the upper bounds on Parts and II.
A.4 Proof of Theorem
From the definition of ranking loss, we have
L K K
E|R ΣΣ
Σ k=j+1
[[((on,())
(b))
Σ Σ (xT,0, < xx
k=j+1
In the rest of the proof, bound each term separately, Specifically, for any list i E [T]] and (j, k) E (K) in it, we have
items
P 0n < xx = (x 0, > 0)
P Ox x, 0n + Aiju Aijik)
P Ox 0, + + - xx 0, Aijik)
P (0, 0.) + x - -0.) Ai.j.k)
A.j.k
A.J.
S P (0, 0.)
+P x,, (0. 00,)
2
In the third equality, we use that A = (xij - x.
TO..
O.. The last step follows from the fact that
event A B > occurs only if c/2 2 B c/2.
Now we bound PP (xT,x (Ō. - 0.) > Ai.jk/2) and note that the other term can be bounded analo- gously. Specifically, we apply Lemmas and 8, and get
P (0, - 0.)
Aijjk
2
A
j. Sdl
S exp
S exp
2
8 8| E.
This concludes the proof.
The above approach relies on the concentration x (Ō. 0.), which is proved Lemma 8. A similar result can be obtained using the Cauchy- -chwaar inequality. This is especially useful when high-proban bigabbrobybylity bound on | 0. 122. already exists, such as in Appendix A.6. Specifically, by the Cauchy-Schwan inequality.
Aijik 2
Ai.ihh
IP (0, - -O.)
< PPP
| II, :100, -O-1LE,
2
A?
PP
||x,,e|| E.
=110,
0.1 12112
4
< P
||0, 0- 1
4d
19

---

In the second inequality, we use that ||x,,<l 22. Finally, Lemma says that
= b S d, which follows from Lemma 2.
P ( 10 0. 12112 2
16d + 8 8log(1/6)
holds for any 8 > 0. To apply this bound, we let
16d + log(1/6)
A A
71
4d
and express 6. This leads to
A i.j.k
A b.j.A
00n - 0.1
S 6 = exp
+ 2d
4d
32d
which concludes the alternative proof.
A.5 Proof of Theorem 5
Following the same steps as Appendix A.3, we have
K(K 1)B
max trA (6.. (0. T.)TA), A,) max
Σ
|all
00,
0.1
E
[E[L]
#E[L]
aeA:
Part
Part
Part I captures the efficiency of data collection and depends on the optimal design. By Lemma 2,
d
|al
Part II measures how the estimated model parameter 6, differs from the true model parameter 0,, under the empirical covariance matrix Σ,, To bound this term, we use Lemma 9 (a restatement of Theorem 4.1 in Zhu et al. [102]) and get that
(d log(1/))
|| 0.112
holds with probability at least 1 - 8, where C >>> 0 is some constant. The main claim follows from combining the upper bounds on Parts and II.
A.6 Proof of Theorem
Following the same steps as in Appendix A.4, we get
PP
x On < x, = P x (b, 0.) + x,,, - -o,) > As.s.)
P 1 (0, -O,) A..j.K)
(1 En -100 - 0. |x,, > Aijuk)
P
(|ZZ,.. E, =100, - 0. 12. 22
< P ||0.
0.112.
In the first inequality, we use the Cauchy-Schwan inequality. the second inequality, we use that j. 12 = mill2i....ll 1: < d, which follows from Lemma 2. Finally, Lemma 9 says that
CK (d + log(1 1011) < 5
P 100 0.1 2
20

---

holds for any 8 > 0. To apply this bound, we let
CK log(1/6))
A
n
d
and express 8. This leads to
A2
A2 L.
PP |0,, 0.12
t.jck
S exp
+ d
d
CK+d
which concludes the proof.
B
Supporting Lemmas
This section contains supporting lemmas and their proofs. Lemma 7, Consider the absolute feedback model in Section 4. Fix E (0, 1). Then
16d + 8 (1/8(1/))
|00, - 0.122, 10.12,11,
holds with probability at least
6.
Proof. Let X knxd be matrix of Kn feature vectors (7) and y E RRKn be a vector of the noise in (I), we can rewrite 0, 0, as
corresponding Kn observations. Under
0, -, = x x (y xe.) xx ' 7
where E IR K' is vector of independent
noise. Now note that a (x (x is fixed vector of length Kn for any fixed Rdd. Therefore, a (Ø, 0.) is sub-Gaussian random variable with a variance proxy
Xx
a (x x a ||a|| x (X x)-1 ||a| x. ./n.
From standard concentration inequalities for Lub-Gaussian random variables [11].
2 2||a| E.
(og(1/5)
P a T(,, 0.)
8
(15)
Y1
holds for any fixed Rd.
To bound || 0.11x.. take advantage of the fact that
Σ1/2 (0,, 0.) A
0 0. Ix (0, 00, 11/2A)
(16)
|10, - 0. 0.11
While A E Rd is random, has two important properties. First, its length is 1. Second, if was fixed, could apply (15) and would get
2 log(1/5)
P 00,
<
To eliminate the randomness in A, we use a coverage argument.
Let S = {a Rd ||a/|2 1} be unit sphere. Lemma 20.1 in Lattimore and Szepesvari [45] says that there exists an s-cover C. C IRd of S that has at most |C.l < (3/s)d points. Specifically, for any E S, there exists y E C. such that ||a ylla I e. By union bound applied to all points in C,, have that
2 log Cog((Cel/0)
P By (0n 0., D4/2
58.
(17)
21

---

Now we are ready to complete the proof. Specifically, note that
100, 0,1|2..
max (On 0., 21/²aa
aES
max min aES yEC.
(0, 0., E1/2(a -a--y y)) + (0,, - 0x, -0,,
-0, /1
||0, 0 Em, la -yll + 2log([Cel/1
max min aES yεC,
n
2 log (Cel/8)
e el 0x >>
7
holds with probability least - 5. this derivation, (a) follows from (16), (b) follows from the Cauchy-Schwarz inequality and (17), and (c) follows from the definition of e-cover C.. Finally, we
rearrange the terms, choose = 1/2, and get that
2 llog((22/0)) S <2V
(2 6)d + 2log(1/6)
0, 0. 11, s 2
n
n
This concludes the proof.
Lemma 8. Consider the absolute feedback model in Section
Fix E RRd and A 0. Then
A
P (xx (Ó.. - 0.) A S exp
2 X
Proof. The proof is from Section 2.2 Jamieson and Jain [33]. Let X E Knxd be matrix of Kn feature vectors in (7) and E R be vector of the corresponding Kn observations. Under noise in (I), can rewrite x" (0,, -0.)
Kn Σ
x xT - 0.) x
X
1
Welh:
1=1
w
where w E KR is fixed vector and v E R is vector of independent sub-Gaussian noise. Then, for any A > and À > we have
P x (0, 0.) A) = P w
A
= P (exp/Aw T nl exp(AA])
Kn
I expl- -AA] II 11
Kn
exp!
HAP[-AAJE
exp
W
Elexp[Awanl]]
1=1
1=1
exp
AA
II
exp
X² w/
/2]
expl - 11
X² 11//221
t=1
(d)
2
A
exp
exp
2| w
2x
X X
x
A
exp
2 X
Σ
In this derivation, (a) follows from Markov's inequality, (b) is due independent noise, (c) follows from aub-Gausiianity, (d) is due to setting A A/|l w| and (e) follows from
| 2 T XX
This concludes the proof.
Lemma 9. Consider the ranking feedback model in Section 5. Fix 8 E (0, 1). Then there exists
constant C 0 such that
CK*(d + log(1
(0g(111) //))
||0, - 1 <
holds with probability at least 1 6-
22

---

Proof. The proof has two main steps.
Step I:
We first prove that e. (0) is strongly means that there exists 7 > such that
with respect the norm
|x, at 0,. This
bx (0. + A) 2 Ln (0.) + (Vi, + +
holds for any perturbation A such that 0_ + A O. To show this, we derive the Hessian of e, (0).
"
K
exp
T (k)) x/,o, (0.00
(0) ni
[ exppx 01
Since ||x|| I and ||0|| S we have expfx TopxxT0) 0) ele_t,ch and thus
expl exp(x] 1 x (1)
e
2 e
2 e
2
EE exppx 10, 0
(K (K--) 1)2 K2
2K(K -) 1)
We further have for any E [n] that
K KK
K
ΣΣΣ EEk
(1) (100))
k=1k==1
K
kl, I.
k==
The last step follows from the fact that oe a permutation. Simply put, we replace the sum of K outer products by all but the ones between the same vectors. Now we combine all claims and get
(n) = 2K(K 1)m
Σ t=1 j=1 k=j+1
21. 21. I.j.A = 7mn
y = f - Therefore, (0) is strongly convex at O. with respect to the norm || -.I....
Step 2: Let 0 = 0, A. Now we rearrange the strong convexity inequality and get
21, (0. A) (..) - (O.,, - -VV,,, A Ve.
(18)
|| |
In the second inequality, we use that ê minimizes e,,, and thus (n + -A) (0.) < 0. In the last inequality, the Cauchy-Schwand inequality.
Next we derive the gradient of the loss function
exp(x (k) 0]
(O)
21, (1,0000))00000
Eim exp (1.)
Zhu al. [102] note that is Bub-Gaussian random variable and prove that
[o.) < CK*(d log(1/))
holds with probability least 1 5, where C is constant. Finally, plug the above bound into (18) and get that
CK* (d+ log log(1/0) || E
n holds with probability at least - 5. We rearrange the inequality and since is a constant,
2 E. || S CK'(d (dgg(1)))))))
log(1/8))
|10, - 00
n
holds with probability at least 8-8 6 for some C > 0. This concludes the proof.
23

---

Method
Maximum prediction error
Ranking loss
Dope (ours)
15.79 = 1.08
0.107 = 0.002
Plug-in (400)
19.75 + 1.48
0.104 + 0.003
Plug-in (300)
30.52 + 3.00
0.103 = 0.002
Plug-in (200)
65.75 13.71
0.114 + 0.003
Plug-in (100)
100.39 + 10.72
0.142 + 0.003
Optimal
9.22 = 0.82
0.092 = 0.002
Table 1: Comparison of Dope with plug-in designs and optimal solution.
C
Optimal Design for Ranking Feedback
The optimal design for (10) is derived as follows. First, we compute the Hessian of &, (0),
K ПEΣD
n K
+ x (0k)0 Tx.
(0) Its exact optimization is impossible because 0_ is unknown. This can be addressed in two ways.
n k=j k'=j (Et,, explx (o.1)) 0) 2 21.0,
Worst-case design: Solve an approximation where f. 0.-dependent terms are replaced with lower bound, We take this approach. Specifically, we show the proof Lemma 9 that
K
K
(0) = 2K(K 1)m
Al..i.ZZ,.ijk = 7
j= kmj+1
for yory=e-4/4 Then we maximize the log determinant of a relaxed problem. This solution is sound and justified, because we maximize lower bound on the original objective.
Plug-in design: Solve an approximation where O. is replaced with a plug-in estimate.
We discuss the pluses and minuses of both approaches next.
Prior works: Mason et al. [55] used plug-in estimate to design a cumulative regret minimization
algorithm for logistic bandits. Recent works on preference-base based learning [102, 20, 99], which are closest related works, used worst-case designs. Interestingly, Das al. [20) analyzed an algorithm with plug-in in estimate but empirically evaluated worst-case design. This indicates that their plug-in design not practical.
Ease of implementation: Worst-case designs are easier to implement. This is because the plug-in estimate does not need to be estimated. Note that this requires solving an exploration problem with additional syper-parameters, such as the number of exploration rounds for the plug-in estimation.
Theory: Worst-case designs can be analyzed similarly to linear models. Plug-in in designs require an analysis of how the plug-in estimate concentrates. The logging policy for the plug-in estimate can be non-trivial as well. For instance, the plug-in estimate exploration in Mason et al. [55] over (dd) special arms, simply get pessimistic per-arm estimates. Their exploration budget is reported in Table 1. The lowest one, for 3-dimensional problem, is 6 536 rounds. This an order of magnitude more than in Figure 1(b) for larger 36-dimensional problem.
Based on the above discussion, we believe that worst-case designs strike good balance between practicality and theory. Nevertheless, plug-in designs are appealing because they may perform well with good plug-in estimate. To investigate this, we repeat Experiment 2 in Section with K (logistic regression). We compare three methods:
(1) Dope: This is our method. The exploration policy is n. in (6).
(2) Plug-in (m): This is a plug-in baseline. For the first m rounds, it explores using policy т. in (6). After that, compute the plug-in estimate of 0, using (10) and solve the D-optimal design with it. The resulting policy explores for the remaining n m rounds. Finally, 0, is estimated from all feedback using (10).
(3) Optimal: The exploration policy म. is computed using the D-optimal design with the unknown 0.. This validates our implementation and also shows the gap from the optimal solution.
24

---

We report both the prediction errors and ranking losses at n = 500 rounds in Table 1. The results are averaged over 100 runs. We observe that the prediction error of Dope is always smaller than that of Plug-in (6 times at m = 100). Optimal outperforms Dope but cannot be implemented in practice. The gap between Optimal and Plug-in shows that an optimal design with a plug-in estimate of 0. can be much worse than that with 0.. Dope has a comparable ranking loss to Plug-in at m = 300 and m = 400. Plug-in has a higher ranking loss otherwise.
Based on our discussion and experiments, we do not see any strong evidence to adopt plug-in designs. They would be more complex than worst-case designs, harder to analyze, and we do not see benefits in our experiments. This also follows the principle of Occam's 's razor, which tells us to design with a minimal needed complexity.
D Related Work
The two closest related works are Mehta et al. [56] and Das et al. [20]. They proposed algorithms for learning to rank L pairs of items from pairwise feedback. Their optimized metric is the maximum gap over L pairs. We learn to rank L lists of K items from K K-way ranking feedback. We bound the maximum prediction error, which is a similar metric to these related works, and the ranking loss in (3), which is novel. Algorithm APO in Das et al. [20] is the closest related algorithmic design. APO greedily minimizes the maximum error in pairwise ranking of L lists of length K = 2. Therefore, Dope with ranking feedback (Section 5.1) can be viewed
generalization of Das et al. [20] to lists of length K > 2. APO can be compared to Dope by applying it to all possible (K) L lists of length 2 created from our lists of length K. We do that in Section 6. The last difference from Das et al. [20] is that they proposed two variants of APO: analyzed and practical. We propose a single algorithm, which is both analyzable and practical.
Our problem can be generally viewed as learning preferences from human feedback [27, 28, 31J. The two most common forms of feedback are pairwise, where the agent observes a preference over two items [12]: and ranking, where the agent observes ranking of the items [65, 54]. Online learning from human feedback has been studied extensively. In online learning to rank [67, 104], the agent recommends a list of K items and the human provides absolute feedback, in the form of clicks, on all recommended items or their subset. Two popular feedback models are cascading [43, 105, 53] and based [44, 23, 100] models. The main difference in Section 4 is that we do not minimize cumulative regret or try to identify the best list of K items. We learn to rank L lists of K items within budget of observations. Due the budget, The main difference is that we do not aim to identify the best arm.
work is related to fxed-budgee BAI [13, 5, 6, 95].
Online learning from preferential feedback has been studied extensively [9] and is often formulated as a dueling bandit [97, 48, 93, 42, 63, 72, 74, 73, 75, 84, 92]. Our work on ranking feedback (Section 5) differs from these works in three main aspects. First, most dueling bandit papers consider pairwise feedback (K = 2) while we study a more general setting of K 2 2. Second, a typical objective in ducling bandits is to minimize regret with respect to the best arm, sometimes in context; either in the cumulative or simple regret setting. We do not minimize cumulative or simple regret. We learn to rank L lists of K items. Finally, the acquisition function in dueling bandits is adaptive and updated in each round. Dope is a static design where the exploration policy is precomputed.
Preference-basee learning has also been studied in a more general setting of reinforcement learning [88, 60, 94, 29]. Preference-basse RL differs from classic RL by learning human preferences through non-numerical rewards [18, 47, 16]. Our work can be also viewed as collecting human feedback for learning policies offline [35, 69, 98, 76]. One of the main challenges of offfine learning is insufficient data coverage. We address this by collecting diverse data using optimal designs [66, 24].
Finally, we wanted to compare the ranking loss in (3) other objectives. There no reduction to dueling bandits. A classic objective in dueling bandits is to minimize regret with respect to the best arm from dueling feedback. Our goal is rank lists. One could think that our problem can be solved as contextual dueling bandit, where each list is represented as a context. This is not possible because the context is controlled by the environment, In our setting, the agent controls the chosen list, similarly to APO in Das et al. [20]. Our objective also cannot be reduced to fixed-budget BAI Our comparisons to Azizi et al. [6] (Sections 4.3 and 5.3) focus on similarities in high-probabillty bounds. The dependence on and d is expected to be similar because the probabilities of making a mistake in
25

---

Number of lists L
100
200
300
400
500
600
700
800
Time (seconds)
4.71
8.31
15.63
21.00
26.60
35.00
41.25
49.72
Table 2: Computation time of policy in (6) as function of the number of lists L.
L 50
L 100
== 200
L 500
K = 2
0.12 0.06
0.28 = 0.12
+.14
0.57 0.21
K = 3
0.06
0.24 = 0.10
0.15
0.50 = 0.19
K = 4
0.13 0.05
0.24 = 0.08
0.35
0.47 0.18
K = 0.12 + 0.04
0.21 = 0.08
0.12
0.45 0.15
Table 3: The ranking loss of Dope as a function of the number lists L and items K.
work and Azizi et al. [6] depend on how well the generalization model is estimated, which the same in both works.
E Ablation Studies
We conduct two ablation studies on Experiment in Section 6.
In Table 2, we report the computation time policy т. in (6). We vary the number of lists L and use CVXPY [21] solve (6). For L 100, the computation takes 5 seconds; and for 800, it takes 50. Therefore, scales roughly linearly with the number of lists L.
In Table 3, vary the number of lists L and items K, and report the ranking loss of Dope. We observe that the problems get harder as L increases (more lists to rank) and casier as K increases (longer lists with more feedback).
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clearly state all contributions and point them from Section 1.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations of our work, such as non-adaptive designs and the lack of lower bounds, are discussed throughout the paper.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All claims are proved in Appendices A and B.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The pseudo-code of the proposed algorithm Dope is given. Experiments described a sufficient detail to be reproducible.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: We did not get permission to release the code.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All details provided in Section 6 and Appendix E.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Standard errors are reported in all plots.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: The computation time is discussed in Section 3 and Appendix E.
9. Code Of Ethics
27

---

Question:
Does the research conducted in the paper conform, in every respect, with the
NeurIPS Code of Ethics
Answer: [Yes]
Justification: We follow the ethics guidelines.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is algorithmic and not tied to any particular application.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This is not applicable to this paper.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: All used assets are stated and cited.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This is not applicable to this paper.
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, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This is not applicable to this paper.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This is not applicable to this paper.
28


Reviews:
[{"review_id": "xHeuWUK8oi", "reviewer": "Reviewer_HJve", "summary": "This paper presents a novel approach for data collection to learn preference models from human feedback. The key innovation is generalizing optimal design, a method for computing information gathering policies, to ranked lists. The authors study both absolute and relative feedback settings, developing efficient algorithms for each and providing theoretical analyses. They prove that their preference model estimators improve with more data, as does the ranking error under these estimators. The work is evaluated on several synthetic and real-world datasets, demonstrating the statistical efficiency of the proposed algorithms. This research contributes to the field by providing a theoretically grounded and empirically effective method for learning preference models from human feedback, with potential applications in areas such as reinforcement learning from human feedback (RLHF) and information retrieval.", "questions": "No.", "limitations": "No.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper extends optimal design theory to ranked lists, introducing a novel approach to preference learning. This is evidenced by the generalization of the Kiefer-Wolfowitz theorem to matrices, providing a strong theoretical foundation for the Dope algorithm.", "weaknesses": "I believe this is a solid piece of work with no obvious errors. From my perspective, considering the following points could potentially strengthen the paper:\n1. In the synthetic experiments (Figures 1a and 1b), the authors only consider the case of L=400 and K=4. Authors should consider different combinations of L and K values to provide a more comprehensive evaluation of the algorithm's performance. In particular, testing cases where K>4 could reveal potential issues arising from the K^6 term in the theoretical analysis. \n2. The paper compares the proposed Dope algorithm to several baselines, but it lacks comparison to more recent and sophisticated methods in preference learning and active learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for positive feedback and acknowledging that our work is solid. We answer all questions below. If you have any additional concerns, please reach out to us to discuss them.\n\n**Q1: Synthetic experiments beyond $L = 400$ and $K = 4$**\n\nWe vary the number of lists and items, $L \\in \\\\{50, 100, 200, 500\\\\}$ and $K \\in \\\\{2, 3, 4, 5\\\\}$, and report the ranking loss of Dope in Experiment 2 (Figure 1b):\n\n| | L = 50 | L = 100 | L = 200 | L = 500 |\n|-|--------|---------|---------|---------|\n| K = 2 | 0.12 ± 0.06 | 0.28 ± 0.12 | 0.37 ± 0.14 | 0.57 ± 0.21 |\n| K = 3 | 0.14 ± 0.06 | 0.24 ± 0.10 | 0.37 ± 0.15 | 0.50 ± 0.19 |\n| K = 4 | 0.13 ± 0.05 | 0.24 ± 0.08 | 0.35 ± 0.14 | 0.47 ± 0.18 |\n| K = 5 | 0.12 ± 0.04 | 0.21 ± 0.08 | 0.34 ± 0.12 | 0.45 ± 0.15 |\n\nWe observe that the problems get harder as $L$ increases (more lists to rank) and easier as $K$ increases (longer lists but also more feedback).\n\n**Q2: Empirical comparison to a recent baseline**\n\nWe compare Dope to a state-of-the-art algorithm APO from\n\n>> Active Preference Optimization for Sample Efficient RLHF. ICML 2024.\n\nThis recent work was suggested by **Reviewer sgSH** and is the closest related work. APO greedily minimizes the maximum error in pairwise ranking of $L$ lists of length $K = 2$. We extend it to $K > 2$ by applying it to all possible ${K \\choose 2} L$ lists of length $2$ created from our lists of length $K$, as described in lines 296-300. We first report the ranking loss in Experiment 2 (Figure 1b) where $K = 4$:\n\n| | n = 10 | n = 20 | n = 50 | n = 100 |\n|-|--------|--------|--------|---------|\n| Dope (ours) | 1.1 ± 0.049 | 0.78 ± 0.029 | 0.48 ± 0.017 | 0.32 ± 0.010 |\n| APO | 1.5 ± 0.057 | 0.99 ± 0.037 | 0.62 ± 0.022 | 0.48 ± 0.021 |\n\nNext we report the ranking loss on the Nectar dataset (Figure 1c) where $K = 5$:\n\n| | n = 50 | n = 100 | n = 200 | n = 500 |\n|-|--------|---------|---------|---------|\n| Dope (ours) | 0.51 ± 0.066 | 0.40 ± 0.053 | 0.29 ± 0.038 | 0.19 ± 0.027 |\n| APO | 1.00 ± 0.120 | 0.98 ± 0.110 | 0.75 ± 0.095 | 0.73 ± 0.100 |\n\nWe observe that Dope has a significantly lower ranking loss than APO. This is for two reasons. First, APO solves the uncertainty reduction problem greedily. Dope solves it optimally, by sampling from an optimal design. Second, APO is designed for $K = 2$ items per list. While it can be applied to our problem, it is suboptimal because it does not leverage the $K$-way feedback that Dope uses.\n\nWe will include all new experiments in the next 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": "cuyMftnrSI", "reviewer": "Reviewer_Chgi", "summary": "This manuscript deals with preference models which are at the crossroads of linear bandits, ranking models, and optimal designs. The authors consider a model where one has to rank L lists of K objects. The expected reward for object k of list i is x_{i,k}\\theta^* and \\theta^* \\in \\mathbb{R}^d is some unknown quantity. They consider two feedback models:  (i) the \"absolute feedback model\" where the learners observes the noisy reward and (ii) the \"ranking feedback model\" where the learner observes an order of the K items sampled from the celebrated Plackett-Luce model.  In the first model, the authors introduce an optimal design with total budget n for estimating the parameter \\theta^* and plug the estimator to bound the error in estimating the L ranking of the K objects. Then, they extend their procedure to the ranking feedback model.", "questions": "1) It is not clear to me to what extent the preference models considered in this manuscript have been previously studied. If it is case, could the authors further discuss this literature? If it is not the case, could the authors explain why the linear assumption with observed x_{i,k} is realistic? \n\n2) It is not clear to me to what extent the rate d^2/n is optimal in Theorem 3. Could the authors discuss this rate?", "limitations": "As explained in the weakness section, I feel that the limitations of using the G-optimal design for ranking purposes are not discussed enough in the manuscript.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) This manuscript introduces an extension of Kiefer-Wolfowitz theorem for building an optimal design in maximum prediction error in linear regression. Although the proof ideas are quite similar to classical Kiefer-Wolfowitz theorem, this result seems to be new. \n\n2) This allows them  control both the prediction error and the ranking error under both feedback models. Both errors seem to be order-wise optimal. \n\n3) The virtue of their procedure compared to adaptive one is that both the experiment design and the computation of the estimators are pretty simple. \n\n4) The authors illustrate the benefits of their procedure compared to e.g. uniform design on small-scale synthetic numerical experiments.", "weaknesses": "1) The purpose of building G-optimal lemmas is to derive tight optimal bounds, However, in this manuscript (Theorems 3--6), the authors only provide order-wise optimal bounds.\n\n1-a) In Theorem 3, the authors establish that the maximum prediction error is of order (up to log) d^2/n. However, for obtaining such a bound, there is no need  to rely on optimal design. Simply using some variant of a uniform design would be sufficient. \n1-b) In Theorem 4, the authors plug the analysis of the OLS for the ranking purpose. However, there is no reason why a G-optimal design should be optimal ranking. Indeed, the ranking loss is not a linear function of the prediction loss. Optimizing the ranking error could therefore require quite different designs. For instance, if two items are extremely difficult to compare, then an optimal ranking design should put further emphasis on this comparison than an optimal prediction design. \n1-c) In generalized linear models, solving the problem (6) does not necessary lead to an optimal prediction design. Still, the author use this approach in Section 5 for ranking feedback. Hence, it is not clear to what extent this design is the most relevant for the prediction purpose. \n\n\n2) Minor remark: Lemma 2 and Theorem 5 require that n  is larger than the number of lists L. This seems to be in contradiction with the regime L >n which is put forward in Section 2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for detailed feedback. We answer all questions below. If you have any additional concerns, please reach out to us to discuss them.\n\n**W1a: Uniform design would suffice to get a $\\tilde{O}(d^2 / n)$ rate in Theorem 3**\n\nWe respectfully disagree. Consider the following example. Take $K = 2$. Let $x_{i, 1} = (1, 0, 0)$ for $i \\in [L - 1]$ and $x_{L, 1} = (0, 1, 0)$, and $x_{i, 2} = (0, 0, 1)$ for all $i \\in [L]$. In this case, the minimum eigenvalue of $\\bar{\\Sigma}_n$ is $n / L$ is expectation, because only one item in list $L$ provides information about the second feature $(0, 1, 0)$. Following the same steps as in Theorem 3, we would get a rate of $\\tilde{O}(d L / n)$. A similar observation was also made in prior works on optimal designs, such as [25] and\n\n>> Best-Arm Identification in Linear Bandits. NeurIPS 2014.\n\n**W1b: Is the optimal design in Section 4 optimal for ranking?**\n\nWe agree with the reviewer that our optimal design may not be optimal for ranking. This is because our ranking bound in Theorem 4 is derived using a prediction error bound. We have not focused solely on the optimal design for ranking because we see value in both prediction (Theorem 3) and ranking (Theorem 4) bounds. The fact that we provide both shows the versatility of our approach. We discuss the tightness of the bound in Theorem 4 after the claim. The dependence on $n$ and $d$ is similar to prior works on fixed-budget BAI in linear models and likely optimal. This is because their probability of making a mistake or a ranking error in our work depends on how well the linear model is estimated, which is the same in both works.\n\n**W1c: Optimal design in Section 5**\n\nThe design is motivated by prior works [7, 106], which showed that the uncertainty can be represented and optimized using outer products of feature vectors. The advantage of these formulations is that they do not contain model-parameter terms, which appear in the Hessian of the log likelihood. Therefore, the optimal design can be solved similarly to linear models. The additional complexity of GLMs is captured through term $\\kappa$ (Assumption 2), which is a lower bound on the derivative of the mean function. This term is common in GLM bandit analyses, although several recent works tried to reduce dependence on it\n\n>> Improved Optimistic Algorithms for Logistic Bandits. ICML 2020.\n\n>> An Experimental Design Approach for Regret Minimization in Logistic Bandits. AAAI 2022.\n\nWe leave tightening of the dependence on $\\kappa$ in our bounds for future work.\n\n**W2: Lemma 2 and Theorem 5 require that $n > L$**\n\nWe do not think so. Can the reviewer be more specific? Both claims contain maximization over lists, $\\max_{i \\in [L]}$, and not a summation, $\\sum_{i = 1}^L$. While the optimized covariance matrix $V_\\pi$ (line 130) involves $\\sum_{i = 1}^L$, the $i$-th term is weighted by the probability that list $i$ is chosen. By the Kiefer-Wolfowitz theorem, the probability distribution that solves the problem is sparse, has at most $d (d + 1) / 2$ non-zero entries.\n\n**Q1: Have our preference models been studied before?**\n\nYes. The absolute feedback model is a variant of a click model (line 92). Click models have been studied in contextual bandits since [110] and\n\n>> Contextual Combinatorial Cascading Bandits. ICML 2016. \n\nThe probability of a click in these papers is a linear function of context and an unknown model parameter. The ranking feedback model is the same as in [106].\n\n**Q2: Optimality of $\\tilde{O}(d^2 / n)$ rate in Theorem 3**\n\nA high-probability upper bound on the prediction error in linear models under the optimal design is\n\n$$|x^\\top (\\hat{\\theta}\\_n - \\theta\\_{\\star})|\n\\leq \\underbrace{||\\hat{\\theta}\\_n - \\theta_*|\\|_{\\bar{\\Sigma}_n}}\\_{\\tilde{O}(\\sqrt{d})} \\cdot\n\\underbrace{||x||\\_{\\bar{\\Sigma}_n^{-1}}}\\_{\\tilde{O}(\\sqrt{d / n})}\n= \\tilde{O}(d / \\sqrt{n})$$\n\nThis bound can be derived by combining (20.3) and Claim 3 in Theorem 21.1, both in [48]. The square of the prediction error is bounded as $(x^\\top (\\hat{\\theta}\\_n - \\theta\\_{\\star}))^2 = \\tilde{O}(d^2 / n)$. The same rate is achieved in Theorem 3. This is optimal since we bound the squared prediction error for $K$ items ($K$ times more than in a classic linear model) from batches of $K$ observations ($K$ times faster learning). The classic setting can be also viewed as $K = 1$.", "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": "OnWe3Ltn1n", "reviewer": "Reviewer_sgSH", "summary": "The paper considers experiment design for collecting ranking/direct feedback, with an application to fine tuning language models.\nAuthor formulate active exploration for fine-tuning as a ranking problem and propose an algorithm which satisfies the standard guarantees for its ranking loss. Experiments on synthetic and real data are provided as a proof of concept, which show that optimal design consistently outperforms random sampling and a number of other vanilla baselines.", "questions": "1. How does the problem of ranking L lists compare to a finite arm (linear) dueling bandit problem with $k$-wise feedback? Is there a reduction from one to another? \n2. How does the ranking problem compare to best-arm-identification for contextual bandits? I'm curious if one can formally show an equivalence between the ranking loss and the BAI sub-optimality gap [e.g. in 1, 2]?\n3. Is dependence on $\\kappa$ in Theorem 6 improvable? I can imagine that $\\kappa$ can get really small exponentially fast?\n\n\n[1] Das, Nirjhar, et al. \"Provably sample efficient rlhf via active preference optimization.\" arXiv preprint arXiv:2402.10500 (2024).\n[2] Azizi, Mohammad Javad, Branislav Kveton, and Mohammad Ghavamzadeh. \"Fixed-budget best-arm identification in structured bandits.\" arXiv preprint arXiv:2106.04763 (2021).", "limitations": "The limitations are discussed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The problem setting applies well to the proposed RLHF/AIHF application. Although this is not used in sota models, but I think the ranking loss gives a strong criteria for fine-tuning.\n\n- The paper is well written. All relevant theoretical guarantees for understanding the algorithm are provided and the rates are compared to previous results.\n\n- Authors provide proof of concept experiments on a large scale AIHF dataset which almost exactly matches their problem setting and demonstrate the benefits of using optimal design.\n\nI think one rarely comes across a paper that manages to deliver on all these criteria.", "weaknesses": "- From a purely theoretical standpoint, I am not sure how novel is the result. I am not particularly familiar with the literature on optimal design. However under slightly different problem setting (e.g. BAI for linear bandits), and the complexity bounds are pretty much common knowledge, even with dueling (k-wise or pair-wise) feedback.\n\n- Some (recent) related work on dueling bandits with function approximation (linear, kernelized, admissible setting) are missing. Particularly [1] proposes a very similar approach: active exploration by maximizing the $\\log\\mathrm{det} V_t$ and MLE for estimation. I put the ones I could think of below.\n\n- I think comparing to other algorithms (not just toy baselines) would really strengthen the story and relevance of the paper. Majority (if not all) of the baselines consider dueling regret (or a sub-optimality gap based on that) but can still be used to learn the reward model for the Nectar or the HH experiment [see 1 & 4]. The data/collection model would be different (e.g. no Lists) but the algorithms can still be evaluated based on the ranking loss to make them comparable to Dope. I think the current way of instantiating a dueling design withing the ranking framework is not realistic.\n\n[1] Nirjhar Das, Souradip Chakraborty, Aldo Pacchiano and Sayak Ray Chowdhury Active Preference Optimization for Sample Efficient RLHF. arXiv preprint, 2024.\n\n[2] Barna Pásztor, Parnian Kassraie, and Andreas Krause. Bandits with Preference Feedback: A Stackelberg Game Perspective. arXiv preprint, 2024.\n\n[3] Johannes Kirschner and Andreas Krause. Bias-robust bayesian optimization via dueling bandits. In International Conference on Machine Learning. PMLR, 2021.\n\n[4] 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, 2023a.\n\n[5] Viraj Mehta, Ojash Neopane, Vikramjeet Das, Sen Lin, Jeff Schneider, and Willie Neiswanger. Kernelized offline contextual dueling bandits. arXiv preprint, 2023b.\n\n[6] Aadirupa Saha. Optimal algorithms for stochastic contextual preference bandits. Advances in Neural Information Processing Systems, 34:30050–30062, 2021\n\n[7] Aadirupa Saha, and Akshay Krishnamurthy. \"Efficient and optimal algorithms for contextual dueling bandits under realizability.\" International Conference on Algorithmic Learning Theory. PMLR, 2022.\n\n[8] Shion Takeno, Masahiro Nomura, and Masayuki Karasuyama. Towards practical preferential bayesian optimization with skew gaussian processes. In International Conference on Machine Learning, pages 33516–33533. PMLR, 2023\n\n[9] Yichong Xu, Aparna Joshi, Aarti Singh, and Artur Dubrawski. Zeroth order non-convex optimization with dueling-choice bandits. In Conference on Uncertainty in Artificial Intelligence. PMLR, 2020\n\n[10] Wenjie Xu, Wenbin Wang, Yuning Jiang, Bratislav Svetozarevic, and Colin N Jones. Principled preferential bayesian optimization. arXiv preprint arXiv:2402.05367, 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for detailed feedback and positive evaluation of the paper. We answer all questions below. If you have any additional concerns, please reach out to us to discuss them.\n\n**W1: Novelty in optimal designs**\n\nA good introduction to optimal designs is Chapter 21 in [48]. At a high level, optimal designs are a tool for computing optimal uncertainty reduction policies. The policies are non-adaptive and thus can be precomputed, which is one of their advantages. Adaptive bandit algorithms can be obtained by combining optimal designs and elimination. A good example is Chapter 22 in [48]. Therefore, solving an optimal design opens the door to other solutions. To the best of our knowledge, this is the first work to study optimal designs in ranking problems, from both absolute and ranking feedback.\n\n**W2: Comparison to related works on dueling bandits**\n\nThank you for the numerous [1-10] references to dueling bandits. To simplify comparison, we focus on three main differences:\n\n**$K = 2$ versus $K > 2$:** All of [1-10] are dueling bandit papers ($K = 2$) while we study a more general setting of $K \\geq 2$.\n\n**Worst-case optimization over lists:** A classic objective in dueling bandits is to *minimize regret with respect to the best arm* from dueling feedback, sometimes in context. This problem can be studied in both cumulative and simple regret settings. The papers [2-3] and [5-10] are of this type. Our goal is to *sort $L$ lists* and the agent controls the chosen list. The works [1] and [4] are closest to our work in this aspect.\n\n**Adaptive versus static design:** All of [1-10] are adaptive designs, where the acquisition function is updated in each round. Dope is a static design where the exploration policy is precomputed. Interestingly, the practical variant of APO in [1] can also be viewed as a static design, because the optimized covariance matrix depends only on the feature vectors of observed lists but not the observations.\n\n**Q1: Reduction of ranking $L$ lists to dueling bandits**\n\nThere is no reduction because the objectives are different. A classic objective in dueling bandits is to *minimize regret with respect to the best arm* from dueling feedback. Our goal is to *sort $L$ lists*. One may think that our problem could be solved as a contextual dueling bandit, where each list is represented as context. This is not possible because the context is controlled by the environment. In our setting, the agent controls the chosen list, similarly to APO in [1].\n\n**Q2: Equivalence of objectives with [1] and [2]**\n\nAlgorithm APO in [1] is indeed the closest related work and we wanted to thank you for bringing it up. APO greedily minimizes the maximum error in pairwise ranking of $L$ lists of length $K = 2$. Therefore, it can be applied to our setting by applying it to all possible ${K \\choose 2} L$ lists of length $2$ created from our lists of length $K$, as described in lines 296-300. We compare to APO next, both empirically and algorithmically.\n\n**Empirical comparison:** We first report the ranking loss in Experiment 2 (Figure 1b) where $K = 4$:\n\n| | n = 10 | n = 20 | n = 50 | n = 100 |\n|-|--------|--------|--------|---------|\n| Dope (ours) | 1.1 ± 0.049 | 0.78 ± 0.029 | 0.48 ± 0.017 | 0.32 ± 0.010 |\n| APO | 1.5 ± 0.057 | 0.99 ± 0.037 | 0.62 ± 0.022 | 0.48 ± 0.021 |\n\nNext we report the ranking loss on the Nectar dataset (Figure 1c) where $K = 5$:\n\n| | n = 50 | n = 100 | n = 200 | n = 500 |\n|-|--------|---------|---------|---------|\n| Dope (ours) | 0.51 ± 0.066 | 0.40 ± 0.053 | 0.29 ± 0.038 | 0.19 ± 0.027 |\n| APO | 1.00 ± 0.120 | 0.98 ± 0.110 | 0.75 ± 0.095 | 0.73 ± 0.100 |\n\nWe observe that Dope has a significantly lower ranking loss than APO. This is for two reasons. First, APO solves the uncertainty reduction problem greedily. Dope solves it optimally, by sampling from an optimal design. Second, APO is designed for $K = 2$ items per list. While it can be applied to our problem, it is suboptimal because it does not leverage the $K$-way feedback that Dope uses.\n\n**Algorithmic comparison:** Dope with ranking feedback (Section 5) can be viewed as a generalization of [1] to lists of length $K \\geq 2$. [1] propose 2 methods: one is analyzed and one is practical. We propose a single algorithm, which is practical and analyzable; and provide both prediction error (Theorem 5) and ranking (Theorem 6) guarantees.\n\nThere is no equivalence of objectives with [2]. Our discussion in lines 207-214 focuses on similarites in high-probability bounds. The dependence on $n$ and $d$ is expected to be similar because the probability of making a mistake in [2] or a ranking error in our work depends on how well the generalization model is estimated, which is the same in both works.\n\n**Q3: Dependence on $\\kappa$ in Theorem 6**\n\nWe briefly discuss this in lines 270-275. Theorem 6 is similar to existing sample complexity bounds for fixed-budget BAI in GLMs. In these bounds, the additional complexity of GLMs is captured through term $\\kappa$ (Assumption 2), which is a lower bound on the derivative of the mean function. This term is common in GLM bandit analyses, although several recent works tried to reduce dependence on it\n\n>> Improved Optimistic Algorithms for Logistic Bandits. ICML 2020.\n\n>> An Experimental Design Approach for Regret Minimization in Logistic Bandits. AAAI 2022.\n\nWe leave tightening of the dependence on $\\kappa$ in our bounds for future work.", "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": "Aden1qNhLD", "reviewer": "Reviewer_f8gc", "summary": "This paper studies the problem of data collection for learning preference models. The key idea is to generalize the optimal design, a method for computing information gathering policies, to ranked lists. The authors study both absolute and relative feedback on the lists.", "questions": "see Weakness.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The considered problem is useful because collecting human feedback is expensive in practice.  \n\n2. The synthetic and real-world experiments show clear advantage of the proposed algorithms while compared with the benchmark methods.\n\n3. This paper is well written and is easy to follow.", "weaknesses": "1. One major concern is the use of optimal design in relative feedback setting. In the absolute feedback case in (1), the optimal design used in (5) is correct as it corresponds to maximizing the metric of fisher information matrix in the least squared regression model. However, in the relative feedback case, the likelihood function is based on a multinomial-type distribution (or logistic-type distribution when $K=2$). In this case, the fisher information matrix is different from the one used in the least squared case. The optimal design for generalized linear models is more challenging than that for the linear models. See below the reference. \n\n{\\it Stufken, John, and Min Yang. \"Optimal designs for generalized linear models.\" Design and Analysis of Experiments 3 (2012): 137-164.}\n\n\n2. I found that some assumptions on the features are missing in the main paper. The main paper does not have any assumption on feature vector $x_{I_t, k}$. However, in the proof of Lemma 8 on line 1072 of page 27, the authors said ``(b) follows from independence of $w_s\\eta_s$\", where $w_s$ and $\\eta_s$ are functions of $x$. In addition, the authors claim that they used the G-optimal design result in [48]. However, [48] considered a ridge regression which guarantees the positive definite of the covariate matrix. However, in the proposed Algorithm 1 (line 11), how do you guarantee the positive definiteness of the sample covariance matrix $\\Sigma_n$?\n\n\n3. Assumption 1 assumes the true parameter belong to the constraint parameter space $\\Theta$ such that $\\theta^T I_d = 0$ and $\\|\\theta\\|_2 \\le 1$. Do you require the estimated parameter also belong to this constraint parameter space $\\Theta$? I did not see how the estimator in (9) satisfies these two constraints. Does the estimator in line 12 of Algorithm 1 have any scaling issue while compared to the true parameter $\\theta^*$ ($\\|\\theta^*\\|_2 \\le 1$)?\n\n4. In the Real-world experiment 3 (Nectar dataset) and Real-world experiment 4 (Anthropic dataset), the authors mentioned that ``During simulation, the ranking feedback is generated by the PL model in (2).\" This indicates that these experiments are not real-world experiments but still synthetic ones. I would suggest to include some benchmark real-world experiments.\n\n\n~~~After rebuttal~~~\nI have increased the score after discussing with the authors during rebuttal stage.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We wanted to thank the reviewer for carefully reading the manuscript, and especially for pointing out how to present the algorithms better. We answer all questions below. If you have any additional concerns, please reach out to us to discuss them.\n\n**W1: Optimal design in Section 5**\n\nThe design is motivated by prior works [7, 106], which showed that the uncertainty can be represented and optimized using outer products of feature vectors. The advantage of these formulations is that they do not contain model-parameter terms, which appear in the Hessian of the log likelihood. Therefore, the optimal design can be solved similarly to linear models. The additional complexity of GLMs is captured through term $\\kappa$ (Assumption 2), which is a lower bound on the derivative of the mean function. This term is common in GLM bandit analyses, although several recent works tried to reduce dependence on it\n\n>> Improved Optimistic Algorithms for Logistic Bandits. ICML 2020.\n\n>> An Experimental Design Approach for Regret Minimization in Logistic Bandits. AAAI 2022.\n\nWe leave tightening of the dependence on $\\kappa$ in our bounds for future work.\n\n**W2: Feature vector and covariance matrix assumptions**\n\nWe assume that the length of feature vectors is at most $1$. This is stated in Assumption 1.\n\nWe also want to explain what $w_s$ and $\\eta_s$ are. In line 1071 (Lemma 8),\n\n$$\n\\underbrace{\\mathbf{x}^{\\top} \\left(\\mathbf{X}^{\\top} \\mathbf{X}\\right)^{-1} \\mathbf{X}^{\\top}}\\_{\\mathbf{w}^{\\top}} \\eta\n= \\mathbf{w}^\\top\\eta\n= \\sum_{s=1}^t w_s\\eta_s$$\n\nwhere $\\eta$ is a vector of independent Gaussian noise up to round $t$. Here $w_s$ and $\\eta_s$ are the components of $\\mathbf{w}$ and $\\eta$. The noise $\\eta_s$ is independent Gaussian and does not depend on the feature vector $\\mathbf{x}$.\n\nWhen data are logged according to the optimal design (Chapter 21 of [48]), the sample covariance matrix in the least-squares estimator may not be full rank. This problem can be solved in multiple ways. In Algorithm 12 (Chapter 22 of [48]), each non-zero entry of the logging distribution is rounded up to the closest integer. This yields at most $d (d + 1) / 2$ extra observations. In our experiments, we add $\\lambda I_d$, for a small $\\lambda > 0$, to line 11 in Algorithm 1. This mostly impacts small sample sizes. Specifically, since the optimal design collects diverse feature vectors, the sample covariance matrix is likely to be full rank when the sample size is large.\n\n**W3: Assumptions on the true and estimated model parameters**\n\nThe reviewer is right. In the model parameter estimator in (9), $\\arg\\min_\\theta$ should be replaced with $\\arg\\min_{\\theta \\in \\Theta}$, where $\\Theta$ is defined in Assumption 1. This change should also be done in line 16 of Algorithm 2 (Appendix F). In short, we need the same assumptions as in [106], from which we borrow the estimator and concentration bound.\n\nOur analysis in Section 4 relies on the concentration bound for non-adaptive designs, in (20.3) of [48], which does not depend on the scale of $\\theta_*$. Therefore, no assumption on $\\theta_*$ is needed in our analysis.\n\n**W4: Semi-synthetic experiments**\n\nThe reviewer is right and we will adjust the language. The models in Anthropic and Nectar experiments are learned from real-world data but the feedback is simulated. We need to simulate to collect independent absolute and ranking feedback when the same list of items is explored multiple times.", "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:

Meta-review: This paper studies the problem of data collection for learning preference models. The key idea is to generalize the optimal design, a method for computing information gathering policies, to ranked lists. The authors study both absolute and relative feedback on the lists.

This paper is borderline, but more on the accept side, based on the reviews and ratings. All reviewers have recommended to accept this paper. 
Also, my understanding is that the authors have addressed most of concerns raised by the reviewers. This paper also has many strengths, as have been pointed out by the reviewers.

Finally, I agree with Reviewer f8gc that this paper should reduce the emphasis on "optimal design" and consider using terms like "active learning" or something similar.
Decision: Accept (poster)