Optimal Design for Human Preference Elicitation

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.

W1: Optimal design in Section 5

The 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

Improved Optimistic Algorithms for Logistic Bandits. ICML 2020.

An Experimental Design Approach for Regret Minimization in Logistic Bandits. AAAI 2022.

We leave tightening of the dependence on $\kappa$ in our bounds for future work.

W2: Feature vector and covariance matrix assumptions

We assume that the length of feature vectors is at most $1$. This is stated in Assumption 1.

We also want to explain what $w_s$ and $\eta_s$ are. In line 1071 (Lemma 8),

\underbrace{\mathbf{x}^{\top} \left(\mathbf{X}^{\top} \mathbf{X}\right)^{-1} \mathbf{X}^{\top}}\_{\mathbf{w}^{\top}} \eta = \mathbf{w}^\top\eta = \sum_{s=1}^t w_s\eta_s$$ where $\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}$. When 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. **W3: Assumptions on the true and estimated model parameters** The 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. Our 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. **W4: Semi-synthetic experiments** The 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.

We thank the reviewer for their response. Our brief response to W1 in the rebuttal was not meant to be "insufficiently rigorous". It goes without saying that we will expand the paper with a discussion of the original problem and our taken approach.

As the reviewer pointed out, our Hessian of the negative log-likelihood is more complex and should be stated. Specifically, let $x_{t, k}$ be the feature vector of the item at position $k$ in the list in round $t$ and $z_{t, k, k'} = x_{t, k} - x_{t, k'}$. Then the Hessian over $n$ rounds is

= \frac{1}{n} \sum_{t = 1}^n \sum_{j = 1}^K \sum_{k = j}^K \sum_{k' = j}^K \frac{\exp[(x_{t, k} + x_{t, k'})^\top \theta]} {2 (\sum_{\ell = j}^K \exp[x_{t, \ell}^\top \theta])^2} z_{t, k, k'} z_{t, k, k'}^\top$$ This is shown in lines 1087-1088 in Appendix. In this work, we maximize the log determinant of relaxed $\nabla^2 \ell_n(\theta_*)$. First, we would like to stress that the exact optimization is impossible unless $\theta_*$ is known. When $\theta_*$ is unknown, two approaches are popular: 1. A plug-in estimate $\hat{\theta}$ of $\theta_*$ is used. The estimate can be computed by a $\theta$-agnostic optimal design and we discuss it later. 2. The $\theta$-dependent term is bounded from below. We adopt the second approach. Following lines 1089-1090 in Appendix, and using our assumptions that $\\|x_{t, k}\\|_2 \leq 1$ and $\\|\theta\\|_2 \leq 1$, we have $$\nabla^2 \ell_n(\theta) \succeq \frac{e^{- 4}}{2 K (K - 1) n} \sum_{t = 1}^n \sum_{j = 1}^K \sum_{k = j + 1}^K z_{t, j, k} z_{t, j, k}^\top$$ Therefore, we can maximize the log determinant of relaxed $$\sum_{t = 1}^n \sum_{j = 1}^K \sum_{k = j + 1}^K z_{t, j, k} z_{t, j, k}^\top$$ which we do in algorithm Dope. This solution is sound and justified, because we maximize a lower bound on the original objective. The last point to discuss is if the alternative approach, maximization of $\nabla^2 \ell_n(\hat{\theta})$ with a plug-in estimate $\hat{\theta}$, could be used. There is no evidence that this approach is practical for the sample sizes of hundreds of human interactions that we consider in our experiments. We start with paper >> An Experimental Design Approach for Regret Minimization in Logistic Bandits. AAAI 2022. which you looked at. Note that this paper is for logistic models only, which is a special case of our setting for $K = 2$. To compute the plug-in estimate, they collect data using optimistic probing in Algorithm 2 based on a G-optimal design for linear models. From the proof of their Theorem 6, $$O\left(d (\log \log d) \frac{C_0}{\Delta_w^{2}} \log\left(\frac{C_0 L}{\Delta_w^2 \delta}\right)\right)$$ samples are needed to compute $\hat{\theta}$, where $L$ is the number of feature vectors and $C_0 \geq 38$. The most favorable setting for this bound is $\Delta_w = 1$ and $C_0 = 38$. Now we instantiate it in our experiments. We take synthetic Experiment 2, where $d = 36$ and $L = 400$. Suppose that we want the claim in Theorem 6 to hold with probability at least $1 - \delta$ for $\delta = 0.05$. Then the suggested sample size is $22043$. This is two orders of magnitude more than our sample sizes in Figure 1b. While this paper does not contain any experiments with real data, the author report the sample sizes of Algorithm 2 in Table 1. The algorithm collects data to compute the plug-in estimate $\hat{\theta}$ and then collects more data using a $\hat{\theta}$-dependent optimal design to initialize a bandit algorithm. The lowest reported sample size for a $3$-dimensional problem is $6536$. This is an order of magnitude more than our sample sizes in Figure 1b for a larger $36$-dimensional problem. Another recent work that sheds light on the performance of plug-in and $\theta$-independent optimal designs is >> Active Preference Optimization for Sample Efficient RLHF. ICML 2024. The authors analyze an algorithm with plug-in estimates but implement a practical one using the outer product of feature vector differences, similarly to our work. This algorithm is only for the setting of $K = 2$.

We thank the reviewer for their response. The reviewer and us agree that the optimal design problem in Section 5 can be solved in two ways:

1. Method A: Solve an approximation where $\theta_*$-dependent terms are replaced with a lower bound (line 1089 in Appendix D.1). We take this approach.
2. Method B: Solve an approximation where $\theta_*$ is replaced with a plug-in estimate. The reviewer would like us to take this approach.

Let's examine the pros and cons of both approaches.

Prior works: Both the reviewer and us pointed to prior works that took our preferred approaches. Therefore, both approaches can be justified by prior works. Recent works on preference-based learning, which are the closest related works, seem to prefer Method A. For example, see

Principled Reinforcement Learning with Human Feedback from Pairwise or K-Wise Comparisons. ICML 2023.

Active Preference Optimization for Sample Efficient RLHF. ICML 2024.

Provable Reward-Agnostic Preference-Based Reinforcement Learning, ICLR 2024

Interestingly, in the second paper, the authors analyze an algorithm with a plug-in estimate akin to Method B. However, the practical algorithm in experiments uses an approximation akin to Method A. This indicates that Method B may not be practical or yield enough practical benefits.

Ease of implementation: Method A is clearly easier to implement. This is because the plug-in estimate in Method B needs to be estimated, which requires solving an additional exploration problem. This also introduces hyper-parameters, such as the number of exploration rounds for the plug-in estimate.

Theory: Method A relies on a linear model theory. Method B requires an analysis of how the plug-in estimate concentrates. The logging policy for the plug-in estimate can be quite involved. For instance, the initial exploration in

An Experimental Design Approach for Regret Minimization in Logistic Bandits. AAAI 2022.

is over $\tilde{O}(d)$ individual arms, simply to get pessimistic per-arm estimates. The exploration budget is reported in Table 1. The lowest one, for a $3$-dimensional problem, is $6536$. This is an order of magnitude higher budget than in our Figure 1b for a larger $36$-dimensional problem. This indicates that a theoretically-sound design of Method B may be too conservative.

Based on the above discussion, we believe that Method A strikes a good balance between practicality with a theory support. We failed to explain in the main paper how the optimal design in Section 5 is approximated. This was an unfortunate omission on our side and we will fix it. All supporting claims are in Appendix D.1 though. We will also stress that the optimal design in Section 5 is not solved optimally. This is not possible and therefore we solve it approximately, as all prior works.

Method B is intriguing because it may perform well with a decent plug-in estimate. The question is whether this would happen within exploration budgets in our paper. To investigate this, we repeat Experiment 2 with $K = 2$ (logistic regression):

• Dope: Explore by the policy in (6) for all rounds.
• Plug-in ($m$): Explore by the policy in (6) for $m$ rounds. After that, we compute the plug-in estimate of $\theta_*$ using (9) and solve the D-optimal design with it. This policy explores for the remaining $n - m$ rounds. Finally, $\theta_*$ is estimated from logged data from all rounds.
• OPT: We solve the D-optimal design with $\theta_*$. This validates our implementation and also shows the gap from the optimal solution.

We report both the prediction errors and ranking losses at $n = 500$ rounds. The gap between Dope and Plug-in was larger for $n < 500$. 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$). OPT outperforms Dope but cannot be implemented in practice. The major gap in the performances of OPT and Plug-in shows that an optimal design with a plug-in estimate of $\theta_*$ can perform much worse than with $\theta_*$. Dope has a comparable ranking loss (within margins of error) to Plug-in at $m = 400$ and $m = 300$. Plug-in has a higher ranking loss otherwise. OPT performs the best again.

Based on our discussion and experiments, we do not see any strong evidence for why we should adopt Method B. It would be more complex than Method A, harder to analyze, and we do not see benefits in our experiments. This also follows the principle of Occam's razor, which tells us to design with a minimal needed complexity.

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.

W1: Novelty in optimal designs

A 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.

W2: Comparison to related works on dueling bandits

Thank you for the numerous [1-10] references to dueling bandits. To simplify comparison, we focus on three main differences:

$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$.

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.

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.

Q1: Reduction of ranking $L$ lists to dueling bandits

There 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].

Q2: Equivalence of objectives with [1] and [2]

Algorithm 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.

Empirical comparison: We first report the ranking loss in Experiment 2 (Figure 1b) where $K = 4$:

Next we report the ranking loss on the Nectar dataset (Figure 1c) where $K = 5$:

We 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.

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.

There 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.

Q3: Dependence on $\kappa$ in Theorem 6

We 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

Improved Optimistic Algorithms for Logistic Bandits. ICML 2020.

An Experimental Design Approach for Regret Minimization in Logistic Bandits. AAAI 2022.

We leave tightening of the dependence on $\kappa$ in our bounds for future work.

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.

W1a: Uniform design would suffice to get a $\tilde{O}(d^2 / n)$ rate in Theorem 3

We 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

Best-Arm Identification in Linear Bandits. NeurIPS 2014.

W1b: Is the optimal design in Section 4 optimal for ranking?

We 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.

W1c: Optimal design in Section 5

The 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

Improved Optimistic Algorithms for Logistic Bandits. ICML 2020.

An Experimental Design Approach for Regret Minimization in Logistic Bandits. AAAI 2022.

We leave tightening of the dependence on $\kappa$ in our bounds for future work.

W2: Lemma 2 and Theorem 5 require that $n > L$

We 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.

Q1: Have our preference models been studied before?

Yes. The absolute feedback model is a variant of a click model (line 92). Click models have been studied in contextual bandits since [110] and

Contextual Combinatorial Cascading Bandits. ICML 2016.

The 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].

Q2: Optimality of $\tilde{O}(d^2 / n)$ rate in Theorem 3

A high-probability upper bound on the prediction error in linear models under the optimal design is

\leq \underbrace{||\hat{\theta}\_n - \theta_*|\|_{\bar{\Sigma}_n}}\_{\tilde{O}(\sqrt{d})} \cdot \underbrace{||x||\_{\bar{\Sigma}_n^{-1}}}\_{\tilde{O}(\sqrt{d / n})} = \tilde{O}(d / \sqrt{n})$$ This 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$.

Thank you for getting back with additional questions.

Tightness of the bounds

We agree with the reviewer that our optimal designs may not be optimal for ranking. 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 also wanted to comment on our solution to the optimal design problem in Section 5. We minimize the prediction error by approximately solving the problem. Specifically:

1. The log likelihood of the original problem, its gradient, and its Hessian are all stated at the following places: (9) for the log likelihood, line 1097 for the gradient (Appendix D.1), and line 1088 for the Hessian (Appendix D.1).
2. The D-optimal design in the relative feedback setting cannot be solved exactly since the model parameter $\theta_*$ in the Hessian is unknown.
3. To get around this issue in GLMs, a common approach is to eliminate $\theta_*$-dependent terms in the uncertainty model. Many works using GLMs in decision making took this approach,

Parametric Bandits: The Generalized Linear Case. NeurIPS 2010.

Provably Optimal Algorithms for Generalized Linear Contextual Bandits. ICML 2017.

Principled Reinforcement Learning with Human Feedback from Pairwise or K-Wise Comparisons. ICML 2023.

Active Preference Optimization for Sample Efficient RLHF. ICML 2024.

Provable Reward-Agnostic Preference-Based Reinforcement Learning, ICLR 2024

4. We replace $\theta_*$-dependent terms with a lower bound (line 1089 in Appendix D.1). As a result, the log determinant of the new Hessian is a lower bound on the original one, and its maximization is a sound and justified way of optimizing the original objective.
5. The penalty for solving the optimal design approximately appears in our claims as a constant of roughly $5$. This is because the norms of $\theta_*$ and feature vectors are all bounded by $1$. We will make this constant explicit in the next version of the paper.

Optimality of $\tilde{O}(d^2 / n)$ rate in Theorem 3

An upper bound on the prediction error in the linear model, when proved through the Cauchy–Schwarz inequality, is

\leq \underbrace{||\hat{\theta}\_n - \theta\_{\star}||\_{\bar{\Sigma}\_n}}\_{\tilde{O}(\sqrt{d})} \cdot \underbrace{||x||\_{\bar{\Sigma}\_n^{-1}}}\_{\tilde{O}(\sqrt{d / n})} = \tilde{O}(d / \sqrt{n})$$ with a high probability. This bound holds for infinitely many feature vectors. The bound can be tightened for a finite number of feature vectors, $m$, to $\tilde{O}(\sqrt{d / n})$, where the $\tilde{O}$ hides $\sqrt{\log m}$. This can be proved using a union bound over (20.3) in Chapter 20 of [48]. When bounding the square of the error, the above bounds become $\tilde{O}(d^2 / n)$ and $\tilde{O}(d / n)$, where the second $\tilde{O}$ hides $\log m$. In Theorem 3, we show that the prediction error is $\tilde{O}(d^2 / n)$. This matches the rate in the linear model and holds for infinitely many lists. The extra factor of $d$ can be eliminated by assuming a finite number of lists.

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.

Q1: Synthetic experiments beyond $L = 400$ and $K = 4$

We 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):

We observe that the problems get harder as $L$ increases (more lists to rank) and easier as $K$ increases (longer lists but also more feedback).

Q2: Empirical comparison to a recent baseline

We compare Dope to a state-of-the-art algorithm APO from

Active Preference Optimization for Sample Efficient RLHF. ICML 2024.

This 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$:

Next we report the ranking loss on the Nectar dataset (Figure 1c) where $K = 5$:

We 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.

We will include all new experiments in the next version of the paper.