Towards Optimality in Active Preference Learning

The gist: The work proposes a novel, instance-dependent experimental design objective for active preference learning that yields an instance-dependent label complexity guarantee, alongside a simple and practical greedy algorithm.

Motivation and Problem Setting

Aligning large language models (LLMs) with human preferences is central to Reinforcement Learning from Human Feedback (RLHF), which relies on pairwise preference learning to fit a reward model. Collecting high-quality human preference labels is expensive and time-consuming, necessitating data-efficient methods that minimize queries while maintaining reward model quality. Existing active learning approaches often adopt classical experimental design criteria like G- or D-optimality, but these are not tailored to the structure of preference learning, leading to suboptimal sampling strategies. The authors argue for an instance-dependent approach, suggesting that pairs of responses with near-ties in preference (i.e., with small reward differences) are the most ambiguous, therefore it is informative to query for them.

Proposed Algorithms and Design Objective

The paper introduces two complementary algorithms based on this intuition. The first algorithm provides the first instance-dependent label complexity guarantee for this setting by proposing a novel experimental design objective. This objective is motivated by analyzing the optimal query allocation in an oracle setting, leading to a unified design that ensures convergence to the true parameter θ∗ at a fast rate. The unified design is defined as λ∗ = arg min λ∈∆(Z) max z∈Z∥z∥(∑z∈Z λzµ˙ (z⊺θ∗)zz⊺)−1∣z⊺θ∗, which differs from G-optimal design by incorporating the instancedependent denominator ∣z⊺θ∗∣.

Active Preference Learning via Experimental Design

The main active learning algorithm, Algorithm 2, proceeds in two phases: a warm-up procedure and a main sequential experimental design procedure. The main phase operates in rounds where an active set Zl is maintained, and a new design λl is computed based on the estimate ˆθl−1 and the active set Zl. The stopping rule for selecting the next batch size Nl involves a term that incorporates both uncertainty reduction and the objective function, defined as f(Zl, ˆθl−1, λ). Theorem 2 provides an upper bound on the label complexity of Algorithm 2, showing it scales as O˜(d/√T). Furthermore, Theorem 3 proves that the reward model ˆθ will classify all arms in Z correctly with a probability of at least 1 − δ.

Simple Greedy Algorithm

A second approach is a simple, practical greedy method motivated by the intuition to use the location of each confidence interval relative to the decision boundary. Algorithm 3 selects the arm with the maximum remaining uncertainty, defined as RUt(z) = min (−LCBt(z),UCBt(z)). This objective is equivalent to max z min −LCBt(z),UCBt(z) = max z Dδ,t(z) − ∣ˆθ⊺t z∣. Theorem 5 demonstrates the advantage of this method over G-optimal based methods on a canonical instance, showing that its label complexity scales as O˜(d + 1/ϵ 2).

Experimental Validation

The proposed method was evaluated on three widely used RLHF preference datasets: the Anthropic helpful and harmless dataset, the Nectar dataset, and the ultrafeedback-binarized-preferences-cleaned dataset. Figure 3 shows that Our proposed method consistently outperforms all baselines on the Anthropic helpful and harmless dataset. The results indicate that the authors' method achieves a balance, performing well early on like D-optimal design but eventually reaching performance comparable to uncertainty sampling.

Conclusion

The work successfully addresses active preference learning by proposing an instance-dependent objective and an efficient greedy algorithm that provides instance-dependent label complexity bounds. This approach moves beyond worst-case guarantees to capture the intrinsic difficulty of a given problem instance. The findings suggest that tailoring experimental design objectives to the specific structure of preference learning problems is crucial for achieving better sample efficiency in RLHF. The paper concludes by noting that future work should investigate how reward model accuracy impacts the aligned LLM performance.

1. Bold header: Instance-Dependent Label Complexity Guarantee

The system can adapt its sampling strategy to the instance-dependent difficulty of the underlying preference learning problem, moving beyond existing approaches that primarily provide worst-case guarantees and do not adapt to the instance-specific difficulty. This allows for more suboptimal sampling strategies when compared to fixed criteria like G-optimality or D-optimality.

2. Bold header: Practical Greedy Algorithm for Active Preference Learning

The system can employ a simple, practical method based on a new uncertainty sampling heuristic that uses the refined objective: max z min −LCBt(z),UCBt(z), which is interpreted as a refined measure of uncertainty for this problem. This avoids solving complex optimization problems and is easy to implement.

3. Bold header: Improved Sample Efficiency in RLHF Alignment

The proposed method can substantially reduce the number of required queries while achieving high reward model accuracy, as shown by the results on real-world datasets. Specifically, it demonstrates that its total label complexity scales as O˜(d + 1/ϵ 2), which is better than the O˜(d/ϵ 2) scaling of G-optimal methods in canonical instances.

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 show the optimality of our instance-dependent term up to a constant depending on the logit bound, compared with a lower-bound characteristic. We evaluate our algorithms on real-world preference datasets and synthetic data observing improved sample efficiency compared to existing methods.