acceptodds
Under review as a conference paper at ICLR 2027

Towards Optimality in Active Preference Learning

Abstract

Aligning large language models (LLMs) depends on high-quality datasets of human preference labels, which are costly to collect. Although active learning has been studied to improve sample efficiency relative to passive collection, many existing approaches adopt classical experimental design criteria such as G- or D-optimality. These objectives are not tailored to the structure of preference learning, leaving open the design of problem-specific algorithms. In this work, we identify a simple intuition specific to preference learning that calls into question the suitability of these existing design objectives. Motivated by this insight, we propose two active learning algorithms. The first provides the first instance-dependent label complexity guarantee for this setting, and the second is a simple, practical greedy method. We evaluate our algorithm on real-world preference datasets and observe improved sample efficiency compared to existing methods.

Primary area:
learning theory
Keywords:
active learning, preference learning, bandit

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_Zun2OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies active preference learning under a realizable linear logistic model. The goal is to identify the preference direction of every response pair in a finite pool using as few labels as possible. The authors propose a margin-aware experimental design algorithm and analyze its instance-dependent label complexity. They also compare the leading complexity term with a KL-based lower bound under bounded logits. A simpler greedy method selects pairs according to their confidence radius minus their estimated absolute margin. Experiments evaluate the methods on synthetic data and human preference data, including preference classification and best-of-NN response selection.

Critical strengths
  1. The sampling objective is well motivated by the classification goal. A pair with a wide confidence interval may already have a clear preference direction if the interval excludes zero. Accounting for the interval’s location gives a concrete reason to move beyond uncertainty reduction alone.

  2. The instance-dependent analysis is useful. The complexity measure captures both the geometry of the feature set and the difficulty of individual comparisons through their margins and Fisher information. The comparison with the KL lower bound helps explain what this measure represents and under which conditions its dependence on the instance is near optimal.

  3. The greedy rule has a clear interpretation and is straightforward to understand. The experiments also consider both held-out preference accuracy and response selection, providing evidence about its usefulness beyond the theoretical identification objective.

Critical weaknesses
  1. My most important concern is that the main text should include the key experimental results. All experiments are currently deferred to the appendix, leaving little empirical evidence in the main paper. For a paper motivated by label-efficient RLHF, these results are important for assessing the practical value of the proposed methods. The main text should present the basic experimental setup and representative results on preference classification and best-of-NN selection. Additional implementation details and supplementary results can remain in the appendix.

  2. The contributions and theoretical results need a clearer presentation. The paper introduces an oracle allocation, a phased experimental design algorithm, and a practical greedy method, but their relationship and respective contributions are not explained clearly enough. The introduction would benefit from a concise account of the main theoretical guarantees, their assumptions, and the precise sense in which the results are instance dependent and near optimal. A clearer explanation of how each algorithm follows from the central intuition would also help readers understand the technical development.

  3. The novelty relative to prior work needs to be articulated more precisely. The paper discusses existing experimental design methods, but the comparison should go beyond differences in their objectives. It should explain which algorithmic components and theoretical arguments are new, which build on existing frameworks, and what additional guarantees are obtained. In particular, a more direct comparison with related work on preference learning and margin-aware pure exploration would help distinguish advances in the problem formulation, sampling strategy, and analysis.

Questions for authors

Could the authors include the key experimental details and results in the main text? Could they also clarify the main algorithmic and theoretical contributions, explain the intuition behind the proposed methods, and provide a more explicit comparison with prior work, as discussed in the Weaknesses section?

4 comments

We thank the reviewer for finding our work well motivated and the instance-dependent analysis useful! Most of the concerns and questions are about presentation, we will address them carefully in the revision.

Experiments.

Thank you for the suggestion. We agree that placing all experimental results in the appendix makes the presentation less ideal. We prioritized the theoretical contributions in the main text. In the revision, we will move the highlighted experimental results to the main text for better visibility.

Clarity.

We will address these clarity issues and make the connection between the oracle, Algorithm 2, and Algorithm 3 more explicit in the paper. In summary, for the algorithmic side contribution,the intuition in Section 3.2 is the starting point: the oracle formalizes the ideal objective as if the true instance were known, Algorithm 2 aims to achieve the optimal leading instance-dependent sample complexity even when the true instance is unknown, and Algorithm 3 provides a more practical approach. For the theoretical side contribution, all existing results we are aware of are worst case only and do not capture instance-dependent behavior, whereas our analysis provides instance-dependent guarantees. We will also add a more detailed comparison with prior work in the related work section, including the comparison perspectives provided by Reviewer 3aMM.

Thank the authors for responding and clarifying. The instance-dependent theoretical results in this paper are interesting to me. Yet I still believe that this paper would benefit much from improving the presentation, especially in the Introduction and Experiments. I strongly encourage the authors to upload a revised version to address the mentioned points to make the work better prepared.

Thank you again for recognizing the value of our instance-dependent theoretical results. We have uploaded a revised one, with particular attention to the following: (1) Introduction: we clarified our contributions and the roadmap from the central intuition to the proposed design, including the connections between the oracle allocation and the two algorithms. (2) Related work: we highlighted the differences between our work and prior work, particularly in the upper-bound guarantees, algorithm adaptivity, and use of confidence intervals. (3) Experiments: we added representative experimental results to the main text.

Thanks the authors for responding. My major concerns have been resolved with the revised version. I would like to keep my positive score.

Reviewer_3aMMOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies sample-efficient active preference learning under a linear logistic model. It proposes an experimental-design algorithm with instance-dependent label-complexity analysis and a practical greedy strategy combining predictive uncertainty with proximity to the decision boundary. The paper compares its leading complexity term with an information-theoretic lower bound and reports improvements in preference classification and best-of-N response selection on synthetic data and Anthropic HH.

Critical strengths
  • The paper characterizes problem difficulty through both feature geometry and preference margins, providing a more informative perspective than worst-case sample-complexity bounds. The comparison with a KL-based lower bound helps explain which instances may benefit from adaptive query allocation.

  • The greedy strategy combines uncertainty with distance to the decision boundary through an easily understood selection criterion. Its implementation avoids the repeated design optimization required by the theoretical algorithm, improving practical accessibility.

  • Evaluation beyond pairwise classification. The experiments include best-of-8 response selection assessed by two reward-model judges, with results averaged over 50 runs. This provides useful evidence that improved data selection can benefit response selection as well as preference prediction.

Critical weaknesses
  • Sampling according to uncertainty and proximity to a decision boundary is closely related to established straddle methods, while related instance-dependent designs already exist for logistic thresholding. The paper should more clearly distinguish its substantive algorithmic and finite-time theoretical advances from these approaches, since this distinction is central to assessing its contribution.

  • The experimental evidence for broader applicability remains limited. The real-data evaluation uses only Anthropic HH with a frozen representation and a linear reward head, while the experimental-design algorithm is evaluated on a single synthetic construction. Although the reported gains are encouraging, these experiments provide limited evidence that the selection criteria remain effective under changes in representation or misspecification of the assumed preference model.

  • Experimental results are absent from the main text. Section 6 only refers readers to Appendix C, leaving the empirical support for the paper’s claims outside the main presentation. The core experimental setup and principal results should be included in the main text so that readers can assess the claimed benefits alongside the theoretical contributions.

Questions for authors
  • What are the principal technical advances over existing level-set estimation and logistic thresholding methods? In particular, which challenges require new theoretical analysis beyond adapting their sampling principles to preference learning?

  • Under what conditions do the exploration and initialization costs remain sufficiently small for the full algorithm to inherit the near-optimality comparison? What theoretical connection can be established between this result and the greedy method evaluated on real data?

  • What evidence supports the robustness of the proposed selection criteria to changes in representation or misspecification of the preference model? Could the core experimental setup and principal results be included in the main text to make the empirical claims directly assessable?

2 comments

We thank the reviewer for finding our instance-dependent guarantee strong and the greedy method easy to understand in practice. We address the weaknesses and questions below.

Level-set estimation and logistic thresholding.

Thank you for providing additional comparison perspectives. For level-set estimation, the closest work we know is ``Nearly Optimal Algorithms for Level Set Estimation'' (AISTATS 2022). Its goal is to identify a set of points where the underlying function exceeds a certain threshold, in our problem, the goal is to return a classifier eventually. Therefore, their results do not directly apply to our setting. For logistic thresholding, it is not clear to us which particular reference the reviewer refers to and would appreciate a pointer. The closest work could be pure exploration in logistic bandits with thresholds. So it falls into the same reason as the level-set estimation case. In this setting, the focus is on distinguishing the best arm, or a near-best arm, from the rest, and a G-optimal-style design objective is well suited to this goal. Estimates of the suboptimal arms themselves can be inaccurate, as their accuracy is not required for best-arm identification. In our setting, the sign of every arm must be estimated correctly, and our design objective explicitly takes this into account. This intuition is discussed in Section 3.2 and leads to the comparison between the key quantities in the upper and lower bounds. In summary, our design objective is tailored to preference learning problem, while prior works on this problem and the off-the-shelf design objectives they used are closer to pure exploration or level-set estimation. We will make this comparison clearer in the revision.

Experimental results location.

We acknowledge that the current page arrangement is not ideal. We prioritized the theoretical contribution, especially the instance-dependent sample complexity, in the main text. In the revision, we will move the highlighted experimental results to the main text.

Exploration and initialization costs.

The upper bound has two main instance-dependent terms, ρ∗\rho^\ast and ρ0\rho_0. The latter accounts for exploration. The key difference is that ρ∗\rho^\ast contains term ∣z⊤θ∗∣2\lvert z^\top\theta^\ast\rvert^2 in the denominator, while ρ0\rho_0 does not. Arms very close to the decision boundary can therefore make ρ∗\rho^\ast large. Or put in a different way, as long as it is not a trivially easy instance (all arms far away from boundary), the exploration cost will be small compared with ρ∗\rho^\ast. We will make this point clearer in the revision.

Theoretical connection between Algorithms 2 and 3.

In Theorem 5, we use the canonical instance to show that the label complexity of Algorithm 3 scales as O~(d+1/ϵ2)\widetilde{O}(d+1/\epsilon^2), compared with O~(d/ϵ2)\widetilde{O}(d/\epsilon^2) for the G-optimal-based method. Plugging the same instance into the leading quantity ρ∗\rho^\ast gives $\rho^\ast=\frac{d-1}{\dot{\mu}(1)} +\frac{1}{\dot{\mu}(\epsilon)\epsilon^2} =\Theta\left(d+\frac{1}{\epsilon^2}\right)$. Thus, Algorithm 3 achieves the same dependence on dd and ϵ\epsilon as the leading quantity in the upper bound for Algorithm 2 and the lower-bound comparison for the problem, up to constants and logarithmic factors.

Robustness of the algorithms.

Model misspecification is beyond the scope of this work. We focus on the realizable setting to study instance optimality and improve on existing work. We will leave this direction for future work.

Thanks for the authors' rebuttal, which has addressed my concerns. I therefore maintain my positive evaluation of this paper.

Reviewer_kEHKOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

the work studies preference learning in the active learning setup for reward model training with human feedback. the goal is to reduce the number of human annotator preferences selection especially when high-quality domain specific labels are needed. According to authors, the currently known G- and D-optomality in experimental design is not sufficient for the position of individual preference pairs relative to the decision boundary. The authors propose and experimental design algorithm with instance-dependent label complexity guarantee and near-optimality results for its leading complexity term under bounded logics, as well as a greedy algorithm that connects confidence width with the preference margin .

Critical strengths
  1. The paper addresses important limitation of existing experimental designs criteria in preference learning, where the reduction of overall parameter uncertainty may not efficiently resolve the preference decisions. Fig 1, wisely present the motivated distinction between confidence interval width and its relative position to the decision boundary.
  2. the proposal of greedy acquisition criterion is simple and easy to implement. The combination of the confidence width and the estimated distance from decision boundary is intuitive and can improve samples efficiency (as suggested in empirical results).
  3. The instance-dependent label-complexity analysis is highly novel
Critical weaknesses
  1. Algorithm 2 was used on constructed synthetic setting, where Algorithm 3 was tested on real-world experiment. The Algorithm 3 doesn't directly inherit the instance-dependent guarantees of Algorithm 2.
  2. Also Algorithm 3 assumes the fixed experimental scope because it relies on confidence intervals defined using Theorem 1, but the greedy algorithm selects samples dynamically, thus I am not sure if the same confidence guarantees holds.
  3. The real world experiments use only one dataset. While results are looking promising, the relative improvement is not strong and would be better to prove it on more datasets/settings. the stronger evidence would definitely benefit the paper.
  4. As point 3 in Strenghts shows, the first contribution is strong, where the second - the greedy algorithm, is way less novel and could be interpreted as close one to the margin- or confidence based sampling algorithms that are well-known.
Questions for authors
  1. I am confused with the preference label information: the feature vector is constructed from chosen and rejected responses, so we can assume that the preference is known in advance, yet in actual AL setting, we need to choose the preference to get to know its label through requested annotations, can authors clarify it?
  2. Please clarify connection between Alghoritms 2 and 3
  3. How exactly are confidence widths computed in Alghorithm 3 and what is the initialization protocol?
2 comments

We thank the reviewer for acknowledging that our paper addresses an important limitation of existing methods and for commenting on the novelty of the instance-dependent complexity analysis. We especially appreciate the comment that Figure 1 presents the idea well. We put a lot of effort into making this idea clear. Given these acknowledgments on strengths, we hope our responses below will help the reviewer reconsider the current weak-rejection rating.

Algorithms 2 and 3.

Both algorithms are motivated by the intuition illustrated in Figure 1. Algorithm 2 focuses on rigorous theoretical guarantees and the first known instance-dependent sample-complexity bound for this problem, while Algorithm 3 emphasizes practical efficiency and simplicity. We do not claim that Algorithm 3 has the same strong theoretical guarantee as Algorithm 2. However, Theorem 5 shows that, on the canonical instance, Algorithm 3 has label complexity O~(d+1ϵ2)\widetilde{O}\left(d+\frac{1}{\epsilon^2}\right), compared with O~(dϵ2)\widetilde{O}\left(\frac{d}{\epsilon^2}\right) for a G-optimal-based selection rule. This shows a clear difference from the straightforward confidence or margin-based principle used by that method, which does not use the location of the confidence interval.

Using only one dataset.

We acknowledge that using only one dataset is a limitation, but the Anthropic HH dataset is a widely used benchmark. We also want to emphasize that our primary goal is theoretical: to provide an instance-dependent sample-complexity guarantee for this setting that fills the gap in the existing design objectives.

Preference label information.

We do not assume that the preference is known in advance. The preference labels are available in the HH dataset (just same as any datasets), the feature vector is simply the difference between the feature representations of the first and second responses. The algorithm selects an arm before its label is revealed. In the experiment, the label is then checked in the dataset to find whether the first or second response is preferred. This mimics active learning process, where the annotation is requested after the arm is selected.

Confidence interval choice

Thank you for paying attention to this detail. The greedy selection rule in Algorithm 3 is written in terms of LCB and UCB on purpose. It can use any confidence intervals that are valid under adaptive sampling. One example is the confidence interval in "A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits" (NeurIPS 2024). We will make this clear in the revision to avoid confusion. In fact, for the instance in Theorem 5, we can even use arm-wise Bernstein confidence bounds to recover the same complexity rates, up to logarithmic factors. For initialization, we use one round-robin pass to pull each arm once, as in many bandit algorithms.

Dear Authors, thank you for addressing all my concerns. I believe with the changes suggested by other reviewers the work will benefit community, I raised my score accordingly.

Comments on the paper

1 comment

We thank all reviewers for their hard work in the review process and for their valuable feedback. We are happy to see the reviewers collectively offer strong words of support for our instance-dependent sample-complexity results. We also appreciate their engagement in the discussion and their confirmation that our responses have addressed their main concerns. We highlight two common points below.

Experimental results in the main text.

Reviewers 3aMM and Zun2 noted that all experimental results were in the appendix. This was due to the page limit. We have carefully rearranged the content, and the revised version now includes representative experimental results in the main text.

Connection between the algorithms.

A second common concern was how the oracle allocation and the two algorithms relate to each other. In our responses to Reviewers kEHK and 3aMM, we clarified the different roles of the algorithms and their theoretical connection on the canonical instance. Following the discussion with Reviewer Zun2, we also revised the introduction to make the connection from the central intuition to the oracle allocation and the two algorithms clearer.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.