Sample Efficient Preference Alignment in LLMs via Active Exploration
Authors: Viraj Mehta
Syrine Belakaria
Vikramjeet Das
Ojash Neopane
Yijia Dai
Ilija Bogunovic
Barbara E Engelhardt
Stefano Ermon
Jeff Schneider
Willie Neiswanger
Venue: COLM 2025 (2025)
Keywords: Sample Efficient
DPO
RLHF
Alignment
Active learning
LLMs
TL;DR: We propose an exploration based approach for active learning for RLHF addressing both online and offline settings

Abstract: Preference-based feedback is important for many applications in machine learning where evaluation of a reward function is not feasible. Notable recent examples arise in preference alignment for large language models, including in reinforcement learning from human feedback (RLHF) and direct preference optimization (DPO). For many applications of preference alignment, the cost of acquiring human feedback can be substantial. In this work, we take advantage of the fact that one can often choose contexts at which to obtain human feedback to most efficiently identify a good policy, and formalize the setting as an \emph{active contextual dueling bandit} problem. We propose an active exploration algorithm to efficiently select the data and provide theoretical proof that it has a polynomial worst-case regret bound. We extend the setting and methodology for practical use in preference alignment of large language models. We provide two extensions, an online and an offline approach. Our method outperforms the baselines with limited samples of human preferences on several language models and four real-world datasets including two new datasets that we contribute to the literature.

Published as a conference paper at COLM 2025
Sample Efficient Preference Alignment in LLMs via Active Exploration
Viraj Mehta* Syrine Belakaria* Vikramjeet Das Ojash Neopane', Yijia Dai Nliaa Bogunovic Barbara Engelhardt', Stefano Ermon Jeff Schneider', Willie Neiswanger
Tennorreeoo 2tannoord, ²CMU, *Cornell, SUCI,, USC
cmu.edu, virajettensorzero. com, syrinebestanford edu, {vdas, oneopane, schneide]@cs. cmu. edu, yd73ecornell. edu, i. www.ooovccuucc.ccoomoomo.ooom. ac. uk, (ermon, begeeeeeeeeeeeeeeeeeeeeeeeeeeee fentnfoordd edu, neiswangeusc.edu
Abstract
Preference-based feedback is important for many applications in machine learning where evaluation of reward function is not feasible. Notable recent examples arise in preference alignment for large language models, including in reinforcement learning from human feedback (RLHF) and direct preference optimization (DPO). For many applications of preference alignment, the cost of acquiring human feedback can be substantial. In this work, we take advantage of the fact that one can often choose contexts at which to obtain human feedback to most efficiently identify good policy, and formalize the setting as an active contextual dueling bandit problem. We propose an active exploration algorithm to efficiently select the data and provide theoretical proof that it has polynomial worst-case regret bound. y
We extend the setting and methodology for practical use in preference alignment of large language models. We provide two extensions, an online and an offline approach. Our method outperforms the baselines with limited samples of human preferences several language models and four datasets including two new datasets that we contribute to the literature.
1 Introduction
The alignment of foundation models with user preferences has gained unprecedented importance due to the widespread utilization of large language models (LLMs). The established pipeline for alignment in LLMs, as outlined in Stiennon et al. (2020) and Ouyang et al. (2022), comprises two steps given pretrained LLM. First, in the Supervised Fine- Tuning (SFT) phase, the LLM undergoes fine-tuning via supervised learning with examples demonstrating the desired behavior. In the second step, Reinforcement Learning from Human Feedback (RLHF), a policy generates multiple completions for each conversation prefix (prompt) in training set; users then give ordinal preferences for the set of completions from a particular prompt. These preferences are used to train a reward model via ranking loss like the Bradley-Terry-Luce model (Bradley & Terry, 1952). Finally, the policy is trained, typically via Proximal Policy Optimization (Schulman et al., 2017), to optimize the reward model while not moving too far from the SFT-trained policy. More recent work (Rafailov et al., 2023), proposed an alternative to RLHF, Direct preference Optimization (DPO), that enables training the LLM policy directly on preference data without using RL and proxy reward model. As LLMs continue to scale and their areas of application broaden, the number of topics on which we need to align increases, as does the overall scale of human- generated training data requirements. Data annotation for preference-basee already incurring a considerable cost for companies that train LLMs. This cost is likely to grow alongside the industry. The issue becomes acute for LLMs in specialized areas such as safety, health, and scientific problems, where the cost of expert feedback can be substantial.
learning is
"qual contribution

---

Published as a conference paper at COLM 2025
In this work, we take advantage of the fact that we have control over which prompts and completions we provide to human experts to make efficient use of their efforts. Drawing recent advancements in active exploration for reinforcement learning (Li et al., 2023) and in black-box optimization (Xu et al., 2020), we introduce a method for assessing the value of collecting preferences specific datapoints, which is both prospective and task- focused. First, we formalize this setting as dueling contextual bandit problem and design an efficient active exploration algorithm that offers polynomial worst-case sample complexity guarantees regarding the policy's performance. Next, we extend these ideas to the alignment setting in LLMs. Weshow that choosing data for training LLM policies on expert preferences can be targeted by active learning, leading to efficient use of resources under restrictive budgets. In this paper, we build atop the DPO methodology (Rafailov et al., 2023), and develop an acquisition strategy that allows us to actively select preference data based on the DPO training objective. We provide two extensions to our active exploration strategy: the first allows online learning approach, where data selection and training are based on the model's s generations, while the second enables the data selection from offline existing data.
We evaluate our methods on four datasets: the Stanford Human Preferences dataset (Etha- yarajh et al., 2022), the Anthropic Helpful-Harmlest dataset (Bai et al., 2022), and two additional datasets which we contribute to the literature: Jeopardy! dataset and Haikus dataset. The Jeopardy! dataset is an extension of an existing dataset from the game show Jeopardy!. It is composed of questions and factual answers evaluate the ability of an alignment method to avoid hallucinations. The Haikus dataset is composed of instruction prompts to write Haikus with specific details and corresponding examples of satisfactory Haikus. We use three LLMs with different sizes CPT-2 (Radford et al., 2019), Pythia- 2.8B (Biderman et al., 2023), and Llama-3-68 (AI@Meta, 2024) to showcase wide range of results and generalization ability. Our full contributions are:
We formalize the problem of preference data selection as a dueling contextual bandit problem and propose an active exploration algorithm to solve it. We provide theoretical analysis on the regret bound of our method.
We propose two extensions of approach to the LLM preference alignment setting: one using online data and another taking advantage of offline data.
We contribute two new datasets to the literature: Jeopardy! and Haikus.
With extensive evaluation, we find that our methods can boost performance by nearly 13% relative to baseline methods when performing preference alignment with restricted human-feedback sample budget and that they outperform the baselines at avoiding hallucinations on our Jeopardy! dataset.
2 Related Work
Learning from Comparative Feedback Reinforcement learning from comparative human feedback has been studied for more than a decade, including work by Fürnkranz et al. (2012), Akour (2014) and, notably, Christiano et al. (2017), which enabled sample-efficient collection of human feedback for deep reinforcement learning (RL) by training a reward model as the RL target. In Appendix D we give a thorough discussion of human feedback in RL and, more recently, L.LMs. However, while effective, using human preference feedback comes with substantial costs, which is reflected in state-of-the-ar work. For example, Ouyang et al. (2022) emphasize RLHF to improve the alignment of GPT--3 across aspects such toxicity, hallucinations, and overall quality. Here, the team enlisted the efforts of 40 labelers and worked with a dataset comprising over 100,000 examples labeled by humans.
Dueling Bandits The bandit literature has also explored the effectiveness of comparative feedback-for example, in the "dueling bandit" setting. This was first studied by Yue et al. (2012) in settings where comparative information is relatively easy to extract but absolute rewards (i.e., direct queries) are ill-defined and have absolute scale. Later, Bengs et al. (2021) surveyed methods that used online learning, where the trade-off with cost of information is most acute, including those used in the online contextual dueling bandit
2

---

Published as a conference paper at COLM 2025
(1) Select context x
(2) Select actions a, a'
(3) Human feedback
Is a'?
Maximmize uncertainty!"
Chhose optimistically."
e
eg is prompe
eg. responses
(4) Update dataset:
D {x, a, a', w]
w
Figure 1: Illustration of the active contextual dueling bandit setting, and its application sample- efficient preference alignment in large language models.
setting by Dudík et al. (2015). These constraints motivate kernelized approach that can incorporate the nonlinearities in the models used in practice.
Active Contextual Bandit Optimization When there exist distinct phases of learning and then deployment, agent can often take steps for improved sample efficiency. For example, in a contextual bandit setting, Char et al. (2019) consider the problem where at test time the goal is to perform well on average across context distribution, while in the learning phase the goal is to choose both contexts and actions for best performance at test-time. The authors propose multi-task version of Thompson sampling during the training phase. We extend this setting from cardinal to ordinal rewards as is appropriate for comparative feedback.
In Li et al. (2023), the agent queries contexts where the value function is most uncertain and acts optimistically. Combined with least-squares value iteration, this method leads to provable polynomial-sample convergence in the worst-case error of the value function estimate in reinforcement learning in general, and as corollary the setting from Char et al. (2019) as a special case. This sets the foundation that we will adapt to the comparative feedback setting.
Uncertainty Estimation in Large Language Models Estimating the epistemic uncertainty in large language models is still active area of research and there are few prior works this topic (focusing specifically on epistemic uncertainty). For example, (Osband et al., 2022) augment existing models with additional layers to model randomness, and subsequently the uncertainty. However performing uncertainty quantification in parallelized fashion requires significant memory overhead. To be more amenable to larger models, we instead model to estimate uncertainty (Gal & Ghahramani, 2016), as
use a dropout-augmentt detailed in Section 5.
In Appendix D, we provide detailed related work about alternative contextual bandit methods, and concurrent work on active selection of data in LLMs.
3 Problem Setting
In this paper, we consider a dueling variant of what we denote the Active Contextual Dueling Bandit (ACDB) problem introduced in Char et al. (2019). An instance of this problem defined by tuple RX f) where X denotes the context space, A denotes the action space and f X x A A [0, 1] is preference function so that f(x, denotes the probability that the action a is preferred to the action a' when the underlying context is We also define domain D = x A. We will design algorithms that operate under the following interaction protocol, which occurs for time steps. During each time step I [T], the agent selects context x, X and a pair of actions a, a A and observes binary random variable w, ~ Be a,, d,)) which equals one a, is preferred to a and zero otherwise. We assume that the preference function has the form
f(x,a,a') = p (r(xx))-((3a -r(xxa)),
(1)
where p IR - [0, 1] is the link function and r D - IR is the wnknown reward function. Common link functions include the logistic function, which leads to the Bradley-Terry-Lue (BTL) model (Bradley& & Terry, 1952) well as the Gaussian CDF (Thurstone, 1927). We also place additional assumptions on the reward function for our theoretical analysis in the kernelized setting (details in Section 4).
3

---

Published as a conference paper at COLM 2025
Our goal is to design algorithms that are able to efficiently identify policies with small suboptimality gap. We define the suboptimality gap of a learner's 's policy π X - A as
SubOpt(z)
sup xeX Mee
-
(2)
This notion of suboptimality (considered in Char et al. (2019) and Li et al. (2023)) is stronger than notions that look at the expected suboptimality of the final policy when the contexts are sampled from some known distribution. In this work we also use this suboptimality, which looks at the worst-case context for each policy. For the kernelized and LLM settings we provide an explicit instantiation of this problem in Section 4 and Section respectively.
4 Active Exploration in the Kernelized Setting
In this section, we describe our first contribution-a theoretically principled algorithm for the ACDB problem- and provide formal guarantees its performance. To provide the theoretical guarantees, we need to first instantiate our general problem setup by making assumptions the preference function f (from Eq. (1)). In particular, we specify class of functions that contain the true unknown reward function. This choice is subtle, as we need to balance the trade-off between our function class's expressiveness and theoretical tractability. Motivated by its theoretical popularity and empirical success, we choose the function class to be a Reproducing Kernel Hilbert Space. While this choice of function class is common in the literature, we make a few additional assumptions to more appropriately accommodate our problem setting.
The Contextual Borda Function Before going over our assumptions, we first introduce the contextual Borda function fr, which is core our algorithm. The contextual Borda function generalizes the Borda function introduced in Xu et al. (2020) for dueling-choice optimization, defined as the probability that an action a will be preferred over a random action a' uniformly sampled from the action space. We generalize this definition to the contextual setting as fr D - [0, 1], where fr (x, = (E [f a, a')) and U(A) is the uniform measure over the action space. It is clear from this definition that fr and r have the same maximizers.
We now discuss our assumptions. Our first assumption restricts the reward and contextual Borda functions to be 'smooth' in a Reproducing Kernel Hilbert Space (RKHS). Our second assumption relates the reward function to the contextual Borda function.
Assumption 4.1. Let k D x D - RR denote a positive semi-definite kernel and let H, denote its associated RKHS. We assume that IIff s B, where B is a known constant.
Note that this assumption is stronger than the standard assumption, which only requires that has a bounded RKHS norm. It is difficult to bound the norm of fr given a bound on the norm of due to the generality of our setting, which allows for different link functions. We investigate this issue numerically in Appendix C. We find that the norm of the Borda function is almost always smaller than the norm of the reward function for samples drawn from the distribution of basis functions used for experiments in Section 6.1.
Assumption 4.2. Let ft (x) max, (x, a) and r"(x) = max, (x, a). There exists a constant L such that for every x X, a E A we have 1 Li (r*(x) - r(x, s (x) (x,
This assumption implies that differences in r will cause a similar magnitude of difference in fr. In fact, when the link function p(.) is Lipschitz continuous, is sufficient for its Lipschitz constant to be at least 1/L, for this condition to hold. We note that this assumption holds for the two most commonly used link functions, the logistic function (Bradley & Terry, 1952) and the Gaussian CDF (Thurstone, 1927).
4.1 Methods
At a high level, our approach reduces the dueling feedback problem to contextual optimiza- tion over single action via the contextual Borda function introduced above. We then apply
4

---

Published as a conference paper at COLM 2025
techniques adapted from recent work on active exploration in reinforcement learning to construct a sampling rule and a policy selection rule, which allow us to output a policy with low suboptimality, Broadly, our sampling rule draws contexts which have maximum uncertainty over the Borda 'value function' and then compares the optimistic action with an action sampled uniformly from the action set.
Estimating the Contextual Borda Function By design, we can estimate the contextual Borda function using preference data (Xt, Kx,,,,,,,, a,, Wr) by selecting x,, in arbitrary fashion and sampling ef uniformly at random. For low dimensional settings, our algorithm first estimates the contextual Borda function using standard kernelized ridge regression (KRR) (Rasmussen et al., 2006). We refer the reader to Appendix A for an explicit description of the KRR regression procedure. In Section 5, we explore modifications of our methods for higher-dimensional settings, such as in the case of L.MSs. One key feature of KRR is that it provides both an estimate of the contextual Borda function after observations, Hr (x,xx,)), as well as uncertainty quantification of the predictions. Indeed, under Assumptions 4.1 and 4.2 we can show that (x, - Hi (x(xx, a)l s Bo, (x,a) a) for an appropriately chosen f and or (x, a) (see Lemma B.1).
Selecting Contexts and Actions Our sampling rule builds on top of the one established in Li et al. (2023) and adapts it to our setting. Their algorithm uses uncertainty estimates over the Q-function to guide exploration. Specifically, at each decision step, the algorithm selects the state where the uncertainty in the value of the best action is highest. Formally, the state maximizes the gap between optimistic and pessimistic Q-value estimates. Then, it chooses the action with the highest optimistic Q-value at that state. This approach focuses exploration on parts of the state space where the agent is most uncertain about which action is best, promoting efficient learning of near-optimal policy. Put simply, the rule is sample the state with the maximum uncertainty over the value function and then act optimistically. We now present our algorithm, which extends these ideas to the dueling setting via the contextual Borda function fr. For now, we assume that there is a known bonus term B/r)) for all We can then define upper and lower confidence bounds fx ax = (r(x, a) + + (x, and f (x, a) = (x(x (/7 o, (x, Our rule is to select context
E arg max (f maxac max
Here, we are choosing a context that maximizes the difference between the optimistic 'value function' and the pessimistic 'value function' (both of which require maximization over actions to compute). We then optimistically choose an action
a, E arg max f (x,, a
After repeating this process T times, we output pessimistic policy against the tightest lower bound we can find, which is the maximizer of all our lower bounds through the optimization process. Put formally, we return fy : - A such that
(x) arg max max, (x,
(5)
aEA
We construct the full active exploration algorithm, AE-Borda, given in Algorithm 1.
4.2 Theoretical Analysis
In this section, we provide our algorithm's theoretical guarantees. We first introduce the maximal-information gain, which plays an important role in our results. The maximum information gain over t rounds, denoted &,, is defined as &, = max A +
εairA), where FA [r(x) EA NO I), and I(X;Y) H(X) H(X is the mutual information. With this definition, we are now ready to state our result.
Theorem 4.3. Suppose we run Algorithm 1 with 2.T) = 2B
200 + 1 log (2) then, with
probability at least 1 - 8, we have that SubOpt($7) s
4
B + T log
5

---

Published as a conference paper at COLM 2025
Algorithm 1 AE-Borda
1: Input: kernel function k(,,), exploration parameters //7), number of inital data ng
2: Let Dmo = (Ni, ai, dip wi) for Ki,aid of drawn uniformly at random.
3: for my +l...,, do
4: Compute n4 (,,,), (t.)) using KRR.
5: Choose x, according to Eq. (3).
6: Choose at according
Eq. (4), draw di U(A), and draw w, Bfrn(f
7: Let = U {(X,, ar dj, wr)
8: end for
9:
Output final policy ft according to Eq. (5).
We provide the proof and discussion of our theoretical results in the appendix.
Scaling Active Exploration to Large Language Models
In order to extend our method to the case where X and A are both large spaces of sequences as common in natural language processing, we must address few limitations of the AE-Borda method presented in Section 4.1:
1. The contextual Borda function fr as defined above is unsuitable for an action space that is extremely large and where most actions are obviously bad (a uniformly sampled sequence of tokens is trivially distinguishable from natural language).
2. Neural network training proceeds in batches, and it would be highly inefficient to label and train on a single example at a time.
3. The uncertainty estimation tools in sequence modeling are more limited than those for explicitly kernelized models, especially due to the memory constraints in training LLMs.
To address these issues, we specialize estimate the uncertainty of our policy using dropout for uncertainty estimation (Gal & Ghahramani, 2016), and perform batched subset selection for our training minibatches. Further, we build atop the foundation presented in Rafailov et al. (2023) on Direct Preference Optimization (DPO), which avoids training separate reward model; this is primarily due to the fact that we prefer to select datapoints based on the estimated uncertainty of the model used for decision making rather than any proxy.
method for the LLM setting. In particular, we
Direct Preference Optimization. Direct Preference Optimization (Rafailov et al., 2023) avoids training a separate reward model based on preferences by instead training the policy directly on pairwise comparison using a loss that optimizes equivalent objective despite functionally behaving like classification. As with PPO (Schulman et al., 2017), this loss depends on reference policy, which we take to be the policy derived from the supervised fine-tuning step, TSFT- The loss is defined LDPO X of RSFT) (xx.a,'', log ( molalx) - log >gpr(a"[x) ]) Rafailov et al. (2023) shows that optimizing this objective 1) (log #spr(a|x)
is equivalent to training a PPO policy with reward function r(x, a) y log xa(alx) (tF](a)
y yoo Zxx) where is the hyperparameter of PPO scaling the KL penalty, Z(x) is partition function, and x, is the policy which optimizes the PPO objective.
5.1 An Acquisition Function for DPO with Online Selection
Given the first limitation defined above, we we propose generalized contextual Borda function:
f (x, a) Ex(-(()) [p(w x, a')]
(6)
for a proposal distribution π X P(A). We note that we can recover the original function by setting x(x) U(A).. As extension of the AE-Borda method, we propose the following

---

Published as a conference paper at COLM 2025
selection rule for the proposal distribution:
Xy arg max maxas A (x, max Asr (x, (x, xeX
(7)
dj E arg max f7 (x,
(8)
We can estimate f,", as well as confidence intervals for any fixed n, using data where a' is sampled from For LLMs f is natural choice for since it will provide meaningful samples. Consequently, we can estimate fr without offline data by asking a labeler to label (x, a,a') where a' πςFT(x) and then fitting 2 with the DPO loss. Assuming that can compute the confidence bounds Ta(a x) and xo(a x) and using the reward expression in the DPO setting, then we can compute f confidence intervals as follows:
P.ASTT (x
(9)
xa(a) n I= 1 + exp (Blog assllaf1x) - Blog xsst(alx))
(a)aa)
MoST Fr. (x, a)
(10)
1=0 exp [Bog
narria x) B Blog 7Sr (a]x)
Ry [x)
Ke (x)
To estimate the confidence intervals of æo, we need estimate its uncertainty. Concretely, we need to address the autoregressive nature of x and We assume consists of ordered tokens I; and log (( x) En s(1; x,1,,..,,(-11) In our method, we use dropout for uncertainty quantification. Specifically, the dropout masks dj are integrated into the function T1; 1x, 4-., dj). During inference, we perform Monte Carlo sampling with dropout, resulting in ensemble with mean:
u(t |x, 4-1)
1
Σ ]E[m]
log Ix, 4.1.dd)
(11)
The standard deviation across this ensemble:
a 11-1)
(logı(1; |x, (.....,,. dj))- n1² [c[m]
Σ
(12)
m -1
serves as an approximation for the model's epistemic uncertainty. This technique allows us to capture uncertainty in computation and memory-efficiet manner without compromis- ing model performance. We then define an acquisition function as
(xx) maXae a Jr (x, a) - maXae (x,a).
(13)
An Algorithm for Active DPO. From here, we the acquisition function in Eq. (13) to choose points that are maximally informative. We do this in batches in order to respect the constraints of training large models. We address this in straightforward fashion, fetching batch of a size much larger than our training batch size, evaluating a, and then choosing the top-b elements. We call our full procedure AE-Borda-DPO, and show details in Algorithm 2.
Extensions to Offline Data. In some real-world settings, practitioners might have offline datasets D ((x,a,a', a', w)} with the context and preference actions predefined. In Ap- pendix we discuss the limitations in using the AE-Borda-DPOO algorithm in this offline setting. We then develop and present an offline active DPO algorithm for these cases.
6 Experiments
We first conduct synthetic experiments to assess the validity our theory, followed by experiments LLMss to show the benefits of our method in practice.
7

---

Published as a conference paper at COLM 2025
Algorithm 2 AE-Borda-DPO
1: Input: Reference policy ZSFT, exploration parameter B, policy constraint weight y, batch
size b, number of iterations N
2: for t= no +1,...,,A do
3: Draw large batch of contexts B = (xi) D.
4: for x; do
5: Sample N actions dij TXST(Xi),, actions dij xx(xi)
6: Estimate ft aij) and fT (x, aij) for each dtj using Eq. (9) and Eq. (10).
7: Compute a(x)).
8:
end for
9:
Let B, be the top-b elements of by a value.
10:
for X; Bi do
11:
Choose action a arg fx aij)
Choose action a/j uniformly over j.
13:
end for
14:
Observe preferences labels and add them to Bj-
15:
Update the policy zo using a gradient step against LDpo using Bi-
end for
17:
Output xa
6.1 Experiments in the Kernelized Setting
In order to assess the validity of our theory we have conducted synthetic experiments that allow us to come as close as possible to the theoretical setting and empirically confirm our results. To do so, implement regression using the BernoulliGP model provided by GPyTorch (Gardner et al., 2018), using a Matérn kernel.
We test distributions of synthetic reward functions generated by sampling a random linear combination of Random Fourier Features (Rahimi & Recht, 2007) derived from squared exponential kernel. For each sampled reward function r, we use the Bradley- Terry model with p(w = a,a', x)) = (=xppr
to generate comparison data. For 25 datapoints and then select data to observe until 500 total datapoints were collected, via one of three methods: AE-Borda: our method, described in Section 4.1, Uniform-BBi -Borda: uniform sampling of both contexts and actions and UCB-Borda: uniform sampling of contexts, along with UCB actions as AE-Borda.
each trial we uniformly sample
This last method reduces to the method presented in (Xu et al., 2020) when naively generalized to the contextual setting. All methods have the same test-time behavior of executing the action found by optimizing the pessimistic Borda function estimate for the test context. By optimizing the ground-truth reward function we were able to approximate the optimal policy and therefore estimate the regret of our policy against it. We give an example of the progression of our method for ID well
Melue emen Oatce
2 2
Sogret
Figure 2: Performance of all methods across 10 random functions with 1D contexts and 1D ac- tions. The left plot shows the median regret across contexts and the right shows the maximum. Error bands show one standard error.
context and 1D actions in Figure as a comparison of iniform-Borda against UCB-Borda in Figure 2. One can see that AE-Borda performs best both on median regret and on the maximum regret, which was the metric of interest in our theoretical analysis.It is clear in Figure 4 that the method is quickly able to concentrate samples in regions that could plausibly be the optimum and that the peaks in the acquisition function over contexts are sensible given the mean and uncertainty estimates of f.. We give a larger set of results showing the progression of AF-Borda in Sec. F.
8

---

Published as a conference paper at COLM 2025
6.2 Experiments using LLMs
To evaluate whether our method is able to improve the selection of data points in DPO, we conduct set of experiments in which we train LLMs on four datasets using three different models of varying sizes. The goal of our empirical study is to see whether improving the data selection strategy causes the downstream policy to perform better on given training task. In order to isolate the effect of the data selection method, we varied the selection method while largely keeping our models and training procedure consistent. In all the experiments in this section, we compare two methods: AE-Borda-DPO, the method we presented in Section 5.1, Uniform-DPO, the method from Rafailov et al. (2023), selecting batches of contexts and their actions uniformly at random, and OAT-DPO, the method from Liu et al. (2024). OAT originally uses a separate reward model. For fair comparison, we adapt it to the DPO setting and use the implicit reward model. The code for our approach is publicly available tit cttuub.combbbee httm/belaaaiiaa///m waaaaativeeeiee weiieee----lmiammmmaeaaeee ignment.
In our training pipeline, first train baseline model using supervised fine-tuning (SFT) on all the supervised data. We add a dropout layer before the penultimate linear layer for our uncertainty estimation mechanism and fine-tune with the dropout activated. Next, we train each of our model-dataset pairs on fraction of the prompts while generating the preference samples from the policy and collecting the preference label using an oracle. We use GPT-4o-min as our training-time oracle.
Pycia
AB-2umia-JJPV
Sastaga Via Bate Over 392
Undoorn. DEO OATIRRO
2.54
B22
Unfom-DeO OXriom
Vitn
Acneage Vitee
Anseage
AB-2umla-PPV Undore
1e-Merde-trr Stmples
Stmrpees
Somples
Semples
AB Parda DEO
Unifbrn 7PO
Ansrage Wes Bats Dveer
OXTEPO
Aoserge Wes thate Diver
Bonda Unitern RPC
Bonda DFO
Hall Ruto Civos
Al Ei-Bett--a Unuteets- BPO
Unitern RPQ
1.
GATEPO
GATODD
DAE
Sumppen
Sumples
Strppies
Figure 3: Active Exploration for DPO in LLMs. For multiple models and datasets we compare AF-Borda-DPO vs Uniform-DPO (Rafailov al., 2023) and OÁT-DPO (Liu al., 2024). In the first six plots we show the average win rate over supervised fine-tuning (SFT), and in the final two plots (on the Jeopardy! dataset) show Null Rate given an incorrect answer (L.A.).
We evaluate both methods on four different datasets. The first two, Anthropic Helpful- Harmless (HH) (Bai et al., 2022) and Stanford Human Prreferences (SHP) (Ethayarajh et al., 2022), are taken from the literature. HH contains examples of two kinds: situations where an assistant needs to be helpful to user asking reasonable question and situations where an assistant should prioritize being harmless as the user is requesting a harmful action. All completions in HH are machine-generater in 18 different categories and consists of broader range of gunan-geeeeated text, but doesn't have the inherent tradeoff of HH. The third dataset is Haikus dataset that we contribute to the literature. is composed of 28,000 instruction prompts to write Haikus with specific details and corresponding examples of satisfactory Haikus.
SHP is dataset of Reddit posts with comments
We also introduce a new Jeopardy! dataset that includes a preference structure capturing aspects of the game while also addressing the question of LLM hallucination. We augment a dataset of 217, 117,000 Jeopardy! questions and answers from HuggingFace (Wolf et al., 2023) with plausible incorrect answer, using GPT-3.5. As in the game show, where points are

---

Published as a conference paper at COLM 2025
deducted for an incorrect response, we embed in the training data that correct answer is preferred to an abstention (the empty string), and both are preferred to the incorrect answer.
We evaluate performance by checking the rate at which the policy produces answers that are preferred to those generated by the initial SFT policy. To assess the win rate, we use GPT-4o judge. We evaluate policies' performance every 2048 training samples for the SHP and Haikus datasets, and every 4096 samples for the Jeopardy! and HH datasets. To mitigate position bias, each pair of responses is evaluated twice, reversing their order in the second evaluation. We then report the average win rate across both evaluations.
We use GPT-2, Pythia-2.8 B, and Llama-3-8B
policies paired with the above datasets to provide wide range of results with varying model sizes and capabilities. We provide extensive evaluation using 8 different experiments: GPT-2 trained on HH, SHP, Haikus, and Jeopardy! datasets, Pythia-2.8 trained on HH and Jeopardy! datasets and Llama-3-8B trained on SHP and Haikus datasets.
In Figure 3, we see that our method AE-Borda-DPO, especially in the later part of our training run, consistently outperforms the standard DPO baseline that samples uniformly. We also notice that it outperforms the OAT baseline in most experiments. We believe this to be due to our acquisition function a, which accounts for the structure of the decision-male maninn problem in choosing which point to query. While we do find our results to be somewhat noisy with high standard error, due to the computational expense of these trials and also the training oracle cost, we were not able to run each experimental baseline for very large number of seeds to further reduce uncertainty in our results.
In the appendix, we provide the win rate for the Jeopardy! experiments. In Jeopardy!, we do not aim for our models to learn to provide correct answers at a higher rate through DPO training. This is because trivia is intended not to generalize easily; in other words, it is difficult to imagine learning that the third US president was Jefferson given training examples of the first two. Instead, we evaluate policies for this dataset on the rate which they abstain for questions ("null rate") where they counterfactually would have been correct vs where they would have been incorrect. Ideally, the policy learned would always abstain where it would have been incorrect and never abstain where it would have been correct. Naturally, this an important goal in the alignment of LLMs and we hope to provide straightforward benchmark for this effort.
For the Jeopardy! dataset, we checked the probability of an empty generation and whether it was the most likely token. We generated nonempty sequence in order to see whether the generated answer was correct, including as a counterfactual in the cases where the method would have abstained. We plot this in Figure 3 (final two plots), where we see that AE-Borda-DPO learns to abstain from answering questions more often when the model would have given the incorrect answer. However, setting is low for both approaches. It is worth noting that the null rates given incorrect answers are higher when using offline data (results shown in Appendix E). This observation indicates that with training on model generations, it is harder to learn to abstain. This is mainly due to the fact that it is not possible to explicitly embed the abstaining preference when we do not have direct control over the preference data. In the appendix, we also provide null rates given the correct answer. We note that the abstaining rate is nearly null for all methods in the case where they would have been correct, which is the desired behavior.
observe that the null rate in the online
7 Summary
In this work, we addressed the problem of how to select contexts and actions at which to obtain human preferences, such that a reinforcement learning agent learns most efficiently. We focus on this problem setting in the context of preference alignment in large language models (LLMs), where collecting data from humans is expensive. The methods developed in this work show promise in reducing these costs. We also make theoretical contribution by giving guarantees on worst-case regret. While our computational study was constrained by the resources available, given our method's 's promising results, we hope to scale up our experimental campaign to greater numbers of GPU resources and DPO steps in the future, to see how our methods perform with larger computational budgets.
10

---

Published as a conference paper at COLM 2025
References
Al@Meta. Llama 3 model card. 2024. URL https::/github..oom to main/MODEL_CARD. md.
Riad Akour. Robust preference learning-based reinforcement learning. 2014.
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. arx preprint (rXiv:2204.05862 2022.
Viktor Bengs, Robert Busa- BusatFekeee, Adil El Mesaoudi-Paul, and Eyke Hüllermeier. Preference- based online learning with dueling bandits: A survey, 2021.
Stella Biderman, Hailey Schoelkopf, Quentin Gregory Anthony, Herbie Bradley, Kyle O'Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, et al. Pythia: A suite for analyzing large language models across training and scaling. In International Conference on Machine Learning, pp. 2397-2430.
PMLR, 2023.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4)3344-45,, 1952.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
lan Char, Youngseog Chung, Willie Neiswanger, Kirthevasan Kandasamy, Andrew Oakleigh Nelson, Mark Boyer, Egemen Kolemen, and Jeff Schneider. Offline contextual bayesian optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' A'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL httph:: https://ppooeeedinggs neur wwtppperpppppppeeeeeeeeeeee.eeee _fierrrfllss/eeleeeeeeeee /2//s/ file//87Gacb66640bad411 f wee3ee1f30c11880 Paper
Xiangning Chen, Chen Liang, Da Huang, Esteban Real, Kaiyuan Wang, Yao Liu, Hieu Pham, Xuanyi Dong, Thang Luong, Cho-Jui Hsieh, et al. Symbolic discovery of optimization algorithms. arXiv preprint ar arXiv:2302.06675 2023.
W. Cho, P. Zhang, Y. Zhang, X. Li, M. Galley, C. Brockett, M. Wang, and J. Gao. Towards coherent and cohesive long-form text generation. 2018.
Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In International Conference on Machine Learning, pp. 844 853. PMLR, 2017.
Paul Christiano, Jan Leike, Tom B Brown, Miljan Martic, Shane Legg, and Dario Amodei.
Deep reinformcement learning from human preferences. In Advmnces in Neural Information Processing Systems 30 (NIPS 2017), 2017. URL https://papers paper/2017 / 44440000000000000004044444444491 Abstract, html.
cc/paper_files/
Nirjhar Das, Souradip Chakraborty, Aldo Pacchiano, and Sayak Ray Chowdhury. Provably
sample efficient rlhf via active preference optimization. aiv preprint a0Xi002402.10500, 2024.
Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. Qlora: Efficient finetuning of quantized Iims, 2023.
Jiuding Duan, Jiyi Li, Yukino Baba, and Hisashi Kashima. generalized model for multidi- mensional intransitivity. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 240-852..55 Springer, 2017.
Miroslav Dudík, Katja Hofmann, Robert E. Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Contextual dueling bandits, 2015.
11

---

Published as a conference paper at COLM 2025
Kawin Ethayarajh, Yejin Choi, and Swabha Swayamdipta. Understanding dataset clfffccutty with VVuusalle information. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Con- ference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 1988-6008. PMLR, 17-23 Jul 2022.
Johannes Fürnkranz, Eyke Hüllermeier, Weiwei Cheng, and Sang-Hyeun Park. Preference- based reinforcement learning: a formal framework and a policy iteration algorithm. Macht Learn, 2012.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In international conference machine learning, pp- 1050-1059. PMLR, 2016.
Jacob R Gardner, Geoff Pleiss, David Bindel, Kilian Q Weinberger, and Andrew Gordon Wil- son. Gpytorch: Blackbox matrix-matrix gaussian process inference with gpu acceleration. In Advances in Neural Information Processing Systems, 2018.
Reinhard Heckel, Nihar B Shah, Kannan Ramchandran, and Martin Wainwright, Active ranking from pairwise comparisons and when parametric assumptions do not help. 2019.
Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models, 2021.
Jonas Hübotter, Sascha Bongni, Ido Hakimi, and Andreas Krause. Efficiently learning at test-time: Active fine-tuning of llms. arXiv preprint ar xrXit:2410.08020, 2024.
Kaixuan Ji, Jiafan He, and Quanquan Gu. Reinforcement learning from human feedback with active queries. arx preprint arXit:2402.09401, 2024.
Kirthevasan Kandasamy, Gautam Dasarathy, Junier Oliva, Jeff Schneider, and Barnabas Poczos. Multi-fidelity gaussian process bandit optimisation. Journal of Artificial Intelligence Research, 66:151-196, 2019.
J. Kreutzer, S. Khadivi, E. Matusov, and S Riezler. Can neural machine translation be improved with user feedback? 2018.
C. Lawrence and S. Riezler. Improving neural semantic parser by counterfactual learning from human bandit feedback. 2018.
Xiang Li, Viraj Mehta, Johannes Kirschner, Ian Char, Willie Neiswanger, Jeff Schneider, Andreas Krause, and Ilija Bogunovic. Near-optimal policy identification in active rein- forcement learning. In The Eleventh International Conference on Learning Representations, 2023. URL https: http:///wwweeieeeeeeoooaaaaaaaaa
Kaizhao Liu, Qi Long, Zhekun Shi, Weijie J Su, and Jiancong Xiao. Statistical impossibility and possibility of aligning Ilms with human preferences: From condorcet paradox to nash equilibrium. arXiv preprint ar arXivo2503.1090
2025.
Zichen Liu, Changyu Chen, Chao Du, Wee Sun Lee, and Min Lin. Sample-efficient alignment for lims. arx preprint ar arXio:2411.01493, 2024.
Volodymyr Mnih. Playing atari with deep reinforcement learning. arv preprint
arXie:1312.5602, 2013.
William Muldrew, Peter Hayes, Mingtian Zhang, and David Barber. Active preference learning for large language models. ar Xiv preprint ar arXiv:2402.08114, 2024.
Ian Osband, Seyed Mohammad Asghari, Benjamin Van Roy, Nat McAleese, John Aslanides, and Geoffrey Irving. Fine-tuning language models via epistemic neural networks. arvio preprint ar (=x:::2211.01555 2022.
12

---

Published as a conference paper at COLM 2025
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- 277444, 2022.
E. Perez, S. Karamcheti, R. Fergus, J. Weston, D. Kiela, and K Cho. Finding generalizable evidence by learning to convince q&a models. 2019.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D. Manning, and Chelsea Finn. Direct preference optimization: Your language model is secretly reward model, 2023.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In J. Platt, D. Koller, Y. Singer, and Roweis (eds.), Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007. URL https: /ttttps:/pprocee pttp//oooceeeecee//ee//epoo/.esp mewpeiiisnnnn.niiiiss.s..... cc/paper_
ftlee//pppee/000011220000000f1f2 (fa Paaaddaa555Pape.pp..... .df..
Carl Edward Rasmussen, Christopher KI Williams, et al. Gaussian processes for machine learning, volume 1. Springer, 2006.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arxiv preprint arXio:1707.06347, 2017.
Nihar Shah and Martin J Wainwright. Simple, robust and optimal ranking from pairwise comparisons. Journal of machine learning research, 18(199):1-38, 2018.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. International Conference on Machine Learning, 2010.
N. Stiennon, L. Ouyang, J. Wu, D. M. Ziegler, R. Lowe, C. Voss, A. Radford, D. Amodei, and P. Christiano. Learning to summarize from human feedback. 2020.
Joe Suk and Arpit Agarwal. Non-stationary dueling bandits under a weighted borda criterion. Xr preprint ar arXi::2403.12950, 2024.
Louis Thurstone. The method of paired comparisons for social values. The Journal of Abnormal and Social Psychology, 21(4))384, 1927.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models, 2023.
Jill Van Newenhizen. The borda method is most likely to respect the condorcet principle. Economic Theory, 2(1)69-83, 1992.
Thomas Wolf, Lewis Tunstall, and Patrick von Platen. Jeopardy dataset, 2023.
Tengyang Xie, Dylan J Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and Alexander Rakhlin. Exploratory preference optimization: Harnessing implicit q"- approximation for sample-efficient rihf. arXiv preprint ar xiv::2205.2 21046, 2024.
Wei Xiong, Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang. Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. In Forty-first International Conference on Machine Learning, 2024.
Yichong Xu, Aparna Joshi, Aarti Singh, and Artur Dubrawski. Zeroth order non-convex op- timization with dueling-choice bandits. In Conference on Uncertainty in Artificial Intelligence, pp. 908. PMLR, 2020.
13

---

Published as a conference paper at COLM 2025
Y. Yue, J. Broder, R. Kleinberg, and T. Joachims. The k-armed dueling bandits problem. 2012.
Shenao Zhang, Donghan Yu, Hiteshi Sharma, Ziyi Yang, Shuohang Wang, Hany Hassan, and Zhaoran Wang- Self-exploring language models: Active preference elicitation for online alignment. Xrv preprint ar wxXio22405.19332 2024.
Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric. P Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. Judging llm-as-a-judge with mt-bench and chatbot arena, 2023.
Daniel M Ziegler, Nisan Stienmon, Jeffrey Wu, Tom B Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human prefer- ences. ar Xiv preprint ar Xix::1999.08593, 2019.
14

---

Published as a conference paper at COLM 2025
Appendix
A RKHS Regression
At step I, have data (4 w1),. ag, wi)). estimate is defined by,
The kernel ridge regression
H4 = arg min Σ
(14)
fEH
1=1
Denote by w, = [Wi...., w,l" the vector of observations, (K))..j=I..... = k(x,, aj)) the data kernel matrix, and (x, = We then have
k(x,, a, X,, a,) the data kernel features.
axxx,a) (x) ( (K, 11,)-1w,
(15)
We further have the posterior variance or, (x, a²² that determines the width of the confidence intervals,
ax, = (xx,))))((xxa) (1)
(16)
B Proof of Theorem 4.3
In this section we will prove our main Theorem, 4.3.
Proof Overview. First, we use standard results on KRR show that our choice of g(r) guarantees that our confidence bands contain (x, a) with high probability simultaneously for all and x, a E X A. Next, we use Assumption 4.2 to show that the suboptimality of the pessimistic policy induced by our estimated contextual Borda function is small whenever we are able to estimate the contextual Borda function well. Finally, we conclude the proof by showing that our sampling rule indeed allows us to estimate the contextual Borda function well. The full proof can be found in Appendix 4.3.
Concrete Performance Bounds. To more concretely understand the performance of our algorithm, we instantiate our results for two commonly studied kernels: the linear and squared-exponential. For both of these settings, the scaling of the information gain is well known (see for example (Srinivas et al., 2010)). In the linear setting, we have that
d Odd leading to bound of O 4
(dlog))). For squared exponential kernels we VT
have 4by 0 (log(T)d+1) leading to suboptimality bound of 0 4 VT
(log(Ty(+1)).
When compared to existing results for dueling bandits (Xu et al., 2020) as well as standard bandits (Chowdhury & Gopalan, 2017), we see that our suboptimality bounds match, thus showing that our algorithm is able to achieve the same performance under a stronger performance metric.
Proof. The overall strategy of the proof is to use our Lipschitz assumption on the link function (more precisely, the relative Lipschitzness of the reward r and the Borda function fr) in order to go to the Borda function, which we can directly model from data. Then, we use our selection criteria as well as confidence bounds taken from Chowdhury & Gopalan (2017) and convergence rates taken from Kandasamy et al. (2019) in order to complete the argument. We give these cited results as lemmas what follows.
In order to attain particular policy performance with probability 1- 8, must bound the error the estimates given by our KRR process for a particular confidence level. In order to do so, we adapt the result from Chowdhury & Gopalan (2017), Theorem 2.
15

---

Published as a conference paper at COLM 2025
Lemma B.1. Let |
2ll
+ Then with probability 1
we have for all time t and any point (x, xXX,,
-x s o-)(xx)).
Proof. To prove this result, will verify that all the conditions from Theorem 2 of Chowdhury & Gopalan (2017) hold. Recall Assumption 4.1 which states that Ilfrll s B. Next, observe that since a, U (A) (independent of everything else), have that
IE [w, F--1] a,), where F, = p (((s,, a,, ws) W=)))=)) is the filtration generated by the past observations. Additionally, since wr E {0, 1} and X,, a, are both Fr-1 measurable, we see that w, can be written as
w, = (x,, Mh,
where 7 is F, condiiilitl subGaussian. Therefore, have met all the necessary conditions, and we can apply Theorem 2 of Chowdhury & Gopalan (2017) which gives us the desired result.
This lemma jointly bounds the modeling introduces a dependence on the RKHS norm of fy. This dependence is inherited from prior work, but empirically study the relationship between the RKHS norm of particular reward function and that of the associated Borda function in Section C.
the Borda function for all time though
We also adapt result from Lemma 8 of Kandasamy et al. (2019) in order to understand the convergence of our uncertainty function o,.
Lemma B.2. Suppose we have queries (q,);, taken from X x A. Then the posterior or satisfies
Σ (
2 log(1+1) 2)
(x A).
Lemma B.2 gives us a handle on how quickly we can expect the uncertainty function to shrink additional datapoints are observed.
Now that we have lemmas B.1 and B.2 in place, we can proceed to the proof of the main result.
16

---

Published as a conference paper at COLM 2025
Proof. In this proof, we condition the event in Lemma B.1 holding true. Given that occurence, we can say the following for every x E X.
Assumption 4.2
S
Li -o
(17)
Lemma B.1
L (xxx max L ((xx
(18)
Def of frr
L ( ma aaaxaammaxxaa mmax ft (x,
(19)
= Li min af maXae f (x, rE[7]
(20)
Lemma B.1
S
Li min
ma max R fr (x,
(21)
TE|T]
Def. of
S
L1 min
(t'),a) a (x a))
(22)
[c[7]
Def. af S
L1 min [E[7]
fx(x'aa)) a') f(()',a))
(23)
T
$
L1
Σ
(((x'aa)) f2(2t,a))
(24)
T
L1 T
Σ 2p or (x(xx,aa)
(25)
/ is increasing 2 (
T
2
Σ o
(26)
T
Sauchy-Schwarz 2L,B2² g(r)
(x),
(27)
T
Lemma B.2 2L (1)
(28)
VT
def of Bb)
2L1
(2B+
2(00 (C (
(29)
vT
L1
1
0
B + Φr
log
(30)
8
C RKHS norms of r and fr
In order to understand the dependence of our estimation bound on the RKHS norm I| we ran numerical experiments on sampled reward functions. For variety of context and action dimensions, we sampled 1000 reward functions as in Section 6.1 and numerically approximated their RKHS norms. We also made a Monte-Carlo estimate of the Borda function fr for each of the reward functions sampled and numerically approximated its RKHS norm. To do this, uniformly sample 1,000 points x; from the input space, compute the regularized kernel matrix K for this set x;, solve the KRR problem Ka = fx) for a. Then
compute the quadratic form Va Ka as an estimate of the RKHS norm.
In Table 1, we present the results of comparing the RKHS norms of 1000 reward functions and their associated Borda functions sampled in Section 6.1. A 'win' was counted when the Borda function had smaller RKHS norm and a 'loss' otherwise. The win margin is the average difference in RKHS norms of the reward and Borda functions, with positive
17

---

Published as a conference paper at COLM 2025
Context Dimension
Action Dimension
Win Rate
Win Margin
1
0.16
-6.3
1
0.89
5.1
3
21.4
1
1
21.5
3
1
38.7
10
10
1
19.6
Table 1: Comparison of RKHS norms of reward functions and associated Borda functions
value when the Borda function was of smaller norm. It is clear here that in general (though not always) the RKHS norm the Borda function fr for a particular reward function is smaller than the RKHS norm of the reward function r itself. This relationship seems to grow stronger as the input dimensionality of the reward function grows larger.
D Additional Related Work
In this section, we discuss additional related work, including alternative contextual bandit methods, uncertainty estimation in large language models, and concurrent work on active selection of data in LLMs.
Human feedback in RL and LLMs Here we discuss additional related work on human feedback in reinforcement learning, and more recently, in LLMs. As described in Section Christiano et al. (2017) enabled sample-efficient collection of human feedback for deep reinforcement learning (RL) by training reward model as the RL target. This technique showed significant performance benefits in practice; for example, in the Atari test case (Mnih, 2013), where naive deep RL would have necessitated thousands accomplished superior performance with just 5,500 or several hours of human queries. More recently, human preference feedback has also been used more recently to improve the performance of LLMs. For example, many recent approaches have demonstrated the effectiveness of using human feedback to enhance LLM stylistic continuation (Ziegler et al., 2019), text summarization (Stiennon et al., 2020), translation (Kreutzer et al., 2018), semantic parsing (Lawrence & Riezler, 2018), review generation (Cho et al., 2018), and evidence extraction (Perez et al., 2019). In particular, the work by (Bai et al., 2022) places focus improving model reliability and robustness by incorporating human feedback to gauge the helpfulness or harmfulness of its responses. However, while effective, the integration of human feedback comes with substantial costs. For example, Stiennon et al. (2020) achieved substantial enhancements over baseline methods but required the generation of summaries for 123,169 posts from the TL,DR dataset, a task performed by a large team of labelers from crowdsourcing platforms. This heavy resource requirement is reflected in state-of-the work. Ouyang et al. (2022) emphasizes RLHF to improve the alignment of the GI'T-3 model across aspects such as toxicity, hallucinations, and overall quality. Here, the team enlisted the efforts of 40 labelers and worked with dataset comprising over 100,000 examples labeled by humans.
hours of gameplay, they
Concurrent work on active learning in LLMs Concurrently with our work, there has been recent releases of papers related to active data selection for LLMs, which we cover in this section. Note that these papers are predominantly recent and yet unpublished work, released on preprint servers, some of which build on our method and setting. For example, Das et al. (2024); Ji et al. (2024) builds on our active contextual dueling bandit setting. Das et al. (2024), aiming to develop method that yields improved theoretical guarantees with reduced assumptions. Zhang et al. (2024) proposed version of DPO using bilevel optimization to optimistically bias towards potentially high-reward responses, though does not explicit uncertainty estimate. Xiong et al. (2024) develops online exploration algorithm as well as a rejection sampling method for offline settings, framing the problem as a reverse-KI. KI. regularized contextual bandit problem. Muldrew al. (2024) propose
18

---

Published as a conference paper at COLM 2025
active learning method for DPO, based on the predictive entropy of LLM predictions as well as uncertainty given by the (implicit) reward model. Xie et al. (2024) presents a method that performs DPO with an exploration bonus for improved efficiency. Finally, Hübotter et al. (2024) work on a method for active selection of examples for fine-tuning of LLMs using active data selection, for (single) given prompt at test time.
E Active DPO Using the Reward Function and Offline Data
In this section, we start by proposing another active learning acquisition function based on the reward model. Then we provide a discussion contrasting the real use cases active learning using online data generated from the policy and the synthetic setting where we can use existing offline benchmarks to evaluate active learning methods.
We propose new acquisition function that uses the confidence interval of the reward function instead of the generalized Borda function that operates based on the preference model. Using the reward model provides an intuitive solution in RLHF in general and DPO in particular, since the goal is to learn a policy that generates high-reward answers. We can approximate the confidence interval for (r and r) using the reward expression the ratio of the policies as defined in the DPO paper. Given the uncertainty estimation method described section 5.1, we can compute our upper and lower bounds
a(x,a) Σ u(t (...,....41)) (o M, log TSF x),
z(x, a)
Σ pli (,44,...,4.1 -1-1--1)-0000 B0 |x, x,41,... (-1)) - log usrgssraa (x),
tr
for an uncertainty parameter B 0. Here, we define acquisition function as:
axx) m(xx,e max,
(31)
In this equation, axx) is the uncertainty of the state-value function according to x. In choosing the states where the potential for error in the value achieved is largest, the agent can learn to behave well in those places. This criterion is similar to that in (Li et al., 2023) and provides similar guarantees to ours for max-regret in the active contextual bandit setting. In situations like ours where we are using fixed offline datasets, set Axx) in Eq. (31) to the set of available responses for a particular action; otherwise, we use Axx = A.
An algorithm for active RLHF/DPO From here, we use the acquisition function in Eq. (31) in order to choose points that are maximally informative. We must do this in batches in order to respect the constraints of training large models. We address this in the naive fashion, pulling larger batch of some size, evaluating a and then choosing the top-b elements in order address this criterion. We refer our full procedure as AE-DPO, and give description in Algorithm 3. Though the use of this acquisition function means that we lose
Algorithm AE-DPO
1: Input: Reference policy ÆSFT, exploration parameter B, policy constraint weight batch size b, number of iterations N
2: for no + +0,,,..... +1, do
3: Draw an unlabeled batch B, = ((xi, di, a;) D.
4: Evaluate axxx)) and let B, be a batch of the top-h elements of B, by value.
5: Collect labels r; and add them to By.
6: Update the policy œe (initialized from the ref.) using gradient step against LDro using B,.
7: end for
8: Output ne
the theoretical guarantees given by the Borda function, we assert that given the rates of convergence associated with kernelized approximations of neural net architectures, we are not giving up strong guarantees in this setting.
19

---

Published as a conference paper at COLM 2025
Ground Truth Borda Punction and Pokcy
Estimated Borda Punction and Policy
1.0
05
0.5
Ariin
0.0
0.0
-0.5
-0.5
-1.0
-1.0
0.0
Costiat
Context
Figure 4: Visualizing the Borda function estimate with 100 data points. Left: the ground truth contextual Borda function fr (red line is the optimal policy). Right: the mean of our posterior estimate of fr (red line is the best policy estimate). Red dots are queries where w, 0 and green are where Wr 1. For full version, Fig.
Algorithms Evaluation on Offline and Online Preference Data The real use case scenario of active learning for preference data would be pairs of data points that differ from any data used during the SFT step (otherwise the SFT labels would be by definition always the preferred action). Therefore, the online approach with AB-Borda- reflects the real use case of active learning. However, prior work on preference learning (Rafailov et al., 2023) makes preferences (e.g. Stanford Human Preferences Dataset (Ethayarajh et al., 2022)). Concurrent active learning work () also uses these datasets to evaluate their approaches in hypothetical scenarios for easier training and evaluations. We do the same and use the offline datasets to evaluate the AE-DPO method. However, evaluating our original AE-Borda-DPa approach on the offline dataset was not feasible due to the acquisition function definition that assumes that the actions selected are not seen by the SFT policy before. Assuming perfect training of the policy on the SFT data (also referred to as chosen answers a), if we evaluate our acquisition function on the existing pair of data, we will have:
proposed in the main paper
of existing offline datasets with labeled
aa
if =1
#SFT (x) (x)
(x)=
a' else
for every point in our dataset. And if we were regress on f. all our labels would be 0 (since ΛSFT is defined as the policy that wins on the dataset). Though this detail is result of properly defined assumptions, prevents us from using the offline labeled data to evaluate AE-Borda-DPO. However, this issue does not occur in the definition of the AE-DPO acquisition function, so we use the offline data for its evaluation.
Additional Experiments for Kernelized Setting
In Figure 5, we depict the progress of the AE-Borda method it continually acquires data. One can see that the estimated optimal policy (red, second row) converges to function quite similar to the ground truth (red, first row) as more data is collected. In addition, it is clear that the selection criterion targets parts of the domain which are relevant to policy learning while avoiding obviously bad regions. We also see in the fourth row that the uncertainty over the value function decreases relatively smoothly across the context space, supporting the idea that our method controls max-regret effectively.
G Additional Experiments for LLMs: AE-Borda-DPO on Jeopardy!
In Figure 6, provide the full experiments Jeopardy! dataset and include the win rate. As discussed in the main paper, the win rate does not improve significantly for any of the methods but the null rate given incorrect answers is higher for AP-Borda-DPO.
20

---

Published as a conference paper at COLM 2025
Time 50
Time 150
Time 600
Genunal Badda Pixxcaan Polas
Ground Banku and Bulec
Trush Sedda und
1.00
0.75
0.75
0.75
0.00
0.30
9.99
0.25
0.25
0.25
0.25
-0.50
-0.50
-0.75
-0.75
-0.75
-1.05
0-0
-3.00
-3.0
0.0
1.0
-1.08
0.0
1.00
bstessie Maria Putcless IMaayy
Coplont
1.40
Extanded Seeda PilAS
Ouslas:
1.00
Istusaled Banda and IMay
0.35
0.25
0.00
0.00
0.00
0.22
-0.29
-0.25
0..50
-0.50
-0.50
1.00
1.60
1.0
1.00
-0.5
1.00
3.50
0.75
0.75
0.75
0.50
0.50
0.50
0.23
0.25
0.25
-0.50
-0.75
-0.5
-0.75
1..00
-1.0
-1.00
0.1
1.0
-1.08
Delimated Bonta Wan Parcttice
Cerfent
Satirwol Wrene Deaction
Contee:
Revmaated Wiin Panetire
Certest
Vilan
Vike
Wiann
CT Vikue
CT Volio
C7 Vikue
3.55
0.1
Hia Sugret
2.5
Saxt Jegre
2.5
Ni Deget
3.5
2.0
1.5
1.0
0.
0.5
0.0
332
40
1200
3.20
1000
2003
2000
300
Timo
Tizze
77700
Figure 5: Progress of AE-Borda across 50, 150, and 600 datapoints. From the top downwards, the charts show the ground truth function, the mean of the posterior estimate of fr, the uncertainty function, the estimate of the value function well as the acquisition function given in Eq. (3), and the regret over time.
21

---

Published as a conference paper at COLM 2025
jngeece
2441 Fate G7T2 jooperty (LA)
GEGP jrogunt
Awanaga Win Date OL 5571
Undiorm-Sro OKT
Not THIN CAwe C.A
AB K7.Bayfa-/39
Tir (infeem-tiin GANDDD
k.30
Utifocn
Samples
Samples
Strppes
Rate 2ythis 10 Josparty (1A)
of Tychia Jospanty ICAA)
AB-dseda-0000
<22
<13.
Nestagg Witn Daae Oheer 577
Utafocmn-31N]
Unilors-Dro
DAT
Not Tata Glaen
AE Bunda DRO Unikeen DPO
OATERO
Stanples
Sangles
Stoglees
Lian Jeepadyy 3.00
Uizmu 28 Jospnnty ICAI
X23
<23
AnNnapa Wie Date Oiver Stry
1.30
Unifeem
DATORO
NoA SEEEN Vee C.A
Undiarn-EPO OXTRRO
2:25
3:30
AB-Munla-IPP
Samples
Samples
Somples
Figure 6: Active Exploration for DPO in LLMs. Experiments run Jeopardy dataset. The plots show the average win rate over supervised fine-tuning (SFT), the Null Rate given an incorrect answer (I.A.) and the Null Rate given a correct answer (C.A.).
H Additional Experiments for LLMs: AE-DPO on Offline Datasets
Given the use of offline data, we do not need an oracle during training. We evaluated the AE-DPO approach on higher number of data points and also against more baselines. To reduce the computational cost of these additional experiments, we applied Qlora to the models used here. In order to evaluate whether our method is able to improve the selection of datapoints in RLHF, we conduct a set of experiments three datasets using one of four methods. The goal of our empirical study is to see whether improving the data selection strategy causes the downstream policy to perform better a given training task. In order to isolate the effect of the data selection method, we vary the selection method while largely holding our model and training procedure consistent. In all the experiments in this section, we compare four methods: DPOAE, the method we presented in Section E; USDPO, which chooses x that maximize variance of the log probabilities of completions: DPO, the method from Rafailov et al. (2023), selecting batches uniformly at random; and SFT, which continues supervised learning with uniformly selected batches. In our training pipeline, we first train baseline model with a Llama-7B (Touvron et al., 2023) architecture using supervised fine-tuning (SFT) on a 40% split of data. We add a dropout layer before the penultimate linear layer for our uncertainty estimation mechanism and fine tune with dropout active. Next, we train using each of the four methods for 100000 samples, evaluating every 2048 samples- each time using our initial SFT trained model as starting point. We give additional information our experimental procedures in Section K.
which we train LLMs
We evaluate these methods on three different datasets. The first two, the Anthropic Helpful- Harmless (HH) dataset (Bai et al., 2022) and the Stanford Human Preferences (SHP) dataset (Ethayarajh et al., 2022), are taken from the literature. We evaluate policies trained on both
22

---

Published as a conference paper at COLM 2025
Averge Correct Pate Skey Hill
Averge Gerret Iate bo 5H17
c.05
017
2.33
6:32
c.08
620
0.00
0.00
1.01
0.22
0.3
0.00
Sunpio
Figure 7: From left: smoothed win rates against preferred choices in dataset of samples generated from each policy end of RLHF training runs across the final four evaluations, and all seeds, on the HH (first) and SHP (second) datasets. In the latter two plots, we force each policy to generate a (non-null) answer, and then, conditional on the answer being correct (fourth) or incorrect (third), plot the rate at which each policy abstains.
of these by checking the rate at which the policy produces answers which are preferred to the chosen completion for the prompt in the dataset.
For the completions generated from the HH and SHP prompts, we use GPT-3.5 (Brown et al., 2020) to generate winners amongst comparisons between the preferred choices given in the dataset. We give the prompts we use for evaluation in Section J. In Figure 2, we see that for the completions in the later part of our training run, AE-DPO performs best among the methods and outperforms US-DPO as well as the other baselines that sample uniformly. We believe this to be due to our acquisition function which accounts for the structure of the decision making problem in choosing which point to query. We do find our results to be noisy due to the computational expense of these trials, were not able to run each experimental baseline for a large number of seeds to further reduce uncertainty in our results.
For the Jeopardy dataset, Similar to AE-Borda-DPO We found that our models do not learn to provide correct answers at higher rate through small amount of DPO training or additional SFT beyond what is required for them to answer the questions. We include an additional exhibit where we the factual nature of this dataset to begin to evaluate the dropout-based uncertainty estimation techniques we use in Appendix K.3.
For the Jeopardy! dataset, we checked the probability of an empty generation and whether it was the most likely token. We generated a nonempty sequence in order to see whether the generated answer was correct, including as a counterfactual in the cases where the method would have abstained. We plot this in Figure 7, where we see that the AE-DPO method is the only method that learns to abstain from answering questions (modestly) more often when the model would have given the incorrect answer. We also find that the standard DPO method quickly learns not to abstain. No methods abstain more than a couple percent of the time in the case where they would have been correct.
For Jeopardy! we also plot the correctness of the policy over time in Figure 8 which shows that no model substantially learns new factual information. Though this is part of the goal of the agent in the Jeopardy! dataset, note that it is not the entire optimization objective, as show in Figure 7. Here, it is clear that no policy is able to improve at predicting correct answers on the test set. This is unsurprising as trivia is a difficult generalization problem.
I The Jeopardy! preference dataset
We generated set of plausible wrong answers for the Jeopardy! dataset from Huggingface (Wolf et al., 2023) by asking GPT-3.5 for a plausible wrong answer given the question, category, and answer. We found that both the category and correct answer were necessary
23

---

Published as a conference paper at COLM 2025
Attrage Stop
0.44
ABLFIPO
IPP
Aweago Tote Donvet
0.38
0.34
5000
10000
13000
20000
25000
3000
Souglex
Figure 8: Rate of correct answers for Jeopardy! over time.
[System]
You are an assistant coming up with plausible but incorrect answers to Jeopardy questions (just the answer, no "what is"). Here 's an example:\n
Q: 'For the last 8 years his life, Galileo was under house arrest for espousing this man 's theory' Category: HISTORY
Correct Answer: Copernicus\n
Response: Brahe [User]
Q: [question]
Category: {category)
Correct Answer: (answer)
Response:
Figure 9: The prompt used to collect plausible wrong answers for Jeopardy! questions.
to include to direct GPT--3.5 generate an answer which was appropriate for the category and to prevent it from accidentally generating a correct answer. We give the prompt used for this process in Figure
J Prompt templates
The prompt templates for GPT-4 as the pairwise comparison evaluation judge and GPT-3.5 as the Jeopardy! single answer correctness judge are listed in Figures 10 and 11. We maintain the standardized prompts proved to be effective by Zheng et al. (2023).
K
Additional Experiment Details
K.1
Experiment details for AE-Borda-DPO evaluation
We train our initial SFT models for epoch for all datasets. We use the models at their full capacity without any quantization. Further, use dropout probability of p 0.05, policy constraint weight 0.1, uncertainty bonus B 4, learning rate of 5 x 10-7 unlabeled batch size 96, and training batch size b of 32. Our implementation was built atop the provided by the authors of the DPO paper (Rafailov et al., 2023).
24

---

Published as a conference paper at COLM 2025
[System]
Please act as an impartial judge and evaluate the quality of the responses provided by two AI assistants to the user question displayed below. You should choose the assistant that follows the user s instructions and answers the user question better. Your evaluation should consider factors such as the helpfulness, relevance, accuracy, depth, creativity, and level of detail of their responses. Avoid any position biases and ensure that the order in which the responses decision. not allow the length of the responses your evaluation. Do not favor certain names as objective as possible. Output your final verdict by strictly following this format: 'A' if assistant A is better, 'B' if assistant is better, and 'c' for tie. Output only that character
presented does not influence your influence
the assistants.
not include any other characters or spaces.
[User Question] (question)
[The Start Assistant A's Answer]
(answer_a)
[The End of Assistant A Answer]
[The Start Assistant Answer]
(answer_b)
[The End of Assistant B Answer]
Figure 10: The default prompt for pairwise comparison.
[System]
You are a judge on whether contestant answer to Jeopardy is correct given a correct answer. If you don tt see the correct answer it is not correct. Answer 'Yes" or 'No' is sufficient. Please don any other words.
[The Start of Correct Answer] (correct_answer, [The End of Correct Answer]
[The Start Contestant Answer] [contestant_answer) [The End of Contestant Answer]
Figure 11: The default prompt for evaluating single Jeopardy! answer.
25

---

Published as a conference paper at COLM 2025
K.2 Experiment details for AE-DPO evaluation
We train our initial SFT models for 1 epoch on the SHP and HH dataset and 2 epochs on the new Jeopardy! dataset. We select the initial training period based on the amount of training after which we obtained validation loss which had plateaued. We also find it reasonable to add dropout layer before the penultimate linear layer since we find that adding a dropout layer not to negatively affect the performance in the SFT phase. To aid in fitting the model on our GPUs, we use QLoRa (Hu et al., 2021; Dettmers et al., 2023) with 4bit quantization for model weights and optimize using the 8-bit Lion optimizer (Chen et al., 2023). For the methods with a reference model, we put the policy and the reference model on two separate GPUs. Further, we use dropout probability of p 0.05, policy constraint weight y 0.1, an uncertainty bonus B 4, learning rate of 5 10-7, an unlabeled batch size of 128, and training batch size b of 32.
K.3 Evaluating dropout-based LLM uncertainty estimation
We believe that in general the estimation of uncertainty for LLMs is an important topic of research and progress there will facilitate a more efficient and informed use of this technology. As we discussed in Section and Section 5, we use dropout- estimation technique to inform the active exploration in this work. Over the course of this study, we considered ensembles and epistemic networks (Osband et al., 2022) as alternative methods for estimating the uncertainty of LLMs. However, each of these methods comes with some additional GPU memory requirement. For epistemic networks, the additional network parameters take GPU memory, while for ensembles, the memory is required to store multiple copies of a network or at least mutiple LoRAs. In our initial studies we found epistemic networks and dropout to perform comparably well and therefore chose dropout due to its smaller memory consumption and good performance. In this section, we explore whether the uncertainties predicted by our estimates differ when the model predicts the correct, incorrect, or null answer and whether these predictions differ in the cases when the model decides to predict null. To do this, we evaluated the log probabilities predicted by ΛSFT on a test set of 20,560 Jeopardy! clues for the correct, incorrect, and null answer. We computed the sample variances over the log probabilities (a x) = E o2 ((-) and plotted their densities in Fig. 12.
uncertainty
We see that the model predicts the highest variances for the log probabilities of incorrect answers. We also see that the the model seems to predict especially low variances for the null token when it decides to output it. The correct answer seems to have lower variance when the model is willing to predict an answer. We see that the log probabilities of incorrect answers always have high variance, indicating high uncertainty. We also see that the null token has a low variance when the model has a non-null output indicating certainty that it should not abstain. The variance further drops when it outputs null, indicating certainty about not knowing an answer. The correct answer has a lower variance than the incorrect answer when the model does not abstain. The relative variances of these two curves support that the model provides meaningful indications of uncertainty. Additionally, in the case where the model abstains, even the correct answer has a high variance, indicating high uncertainty. We believe that these results support that the uncertainty function is at least correlated with the model's knowledge about the input. This offers support to the hypothesis that our estimates of the variance are somewhat meaningful. However, we believe that this is an important research topic and warrants substantial further study under variety of lenses. We hope that this work will encourage further research in this area.
L Intransitivity and Condorcet paradox
It is important to note that intransitivity and the presence of Condorcet paradoxes- as discussed in (Liu et al., 2025; Duan et al., 2017) are important considerations when using preference-based methods. Our proposed Borda function is rooted in the classical Borda score/ ccuntt method and therefore inherently overcomes these issues (Heckel et al., 2019). The Borda score aggregates over pairwise comparisons, which helps mitigate the impact of
26

---

Published as a conference paper at COLM 2025
Variance when model outputs non-null answer
Variance when model outputs mull
Correct
Correct
Incorrect
Incorrect
Null
Null
6
6
5
5
Density
Density
3
3
2
2
0
0
0.0
0.2
0.4 Variance
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Variance
Figure 12: Density of (r(a |xx conditioned correct, incorrect, and null values for The left hand plot depicts the variance distributions conditional on the model outputing non-null completion, while the right hand is conditional on a null completion.
local inconsistencies or cycles that may arise due to intransitivity. Because the contextual Borda function marginalises over all opponents, should be immune to cycles in the comparison graph and is always defined, even when pairwise preferences are intransitive (Shah & Wainwright, 2018).
As for the Condorcet paradox, whenever a Condorcet winner exists, it would maximise the Borda function (Van Newenhizen, 1992); otherwise, the maximizer should provide regret. While the Borda rule is not
the standard compromise used in duelling- immune to the Condorcet paradox, it is known to produce robust ranking in practice (Shah& Wainwright, 2018; Heckel et al., 2019). Recent related work points out that while the Condorcet winner may not always exist, the Borda winner is always well-defined (Suk& Agarwal, 2024). We view the use of Borda-based selection as a pragmatic and computationally efficient solution, particularly suitable for the early stages of exploration when uncertainty high and perfect transitivity is unlikely.
27


Reviews:
[{"review_id": "NmEP6sZiIT", "reviewer": "Reviewer_JaHM", "summary": "This paper consider the active contextual dueling bandit problem in the context of LLM alignment, where the system can control both the prompts and the model responses presented to a human expert. The authors propose a UCB-style algorithm aimed at achieving sample-efficient alignment, by adaptively selecting prompts and responses to obtain informative human labels. Experimental results shows improved performance over baseline methods under the same query budget.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The topic of this paper is interesting and important. The paper addresses a practically setting for LLM preference alignment, where the human expert provides feedback and the prompts are controllable. This contrasts with the more commonly studied online serving scenario, where prompts are user-generated and not under the model designer's control. Designing algorithms tailored to different operational constraints is essential, particularly in alignment tasks, where human feedback is expensive and the scale of deployment can be large.\n\nThe paper is generally well-written and easy to follow. The figures are informative and help clarify the method.", "reasons_to_reject": "The paper omits comparison to some relevant prior work. For instance, Liu et al. consider a similar setting and propose methods to improve sample efficiency under both exploration–exploitation and pure exploration setting. The pure exploration setting in Liu et al. seems to share the same objective as this paper. Moreover, the proposed algorithm in this work shares a similar motivation and structure. Since this paper assumes control over prompts, which is a stronger assumption than in Liu et al., I would expect a direct comparison, and possibly better performance.\n\nLiu, Zichen, et al. \"Sample-efficient alignment for llms.\" arXiv preprint arXiv:2411.01493 (2024).", "questions_to_authors": "Dropout-based uncertainty estimation is known to be unreliable in large-scale deep models (Lakshminarayanan et al. 2017). Have you evaluated the quality of uncertainty estimates? This seems critical to assess whether the observed sample-efficiency improvements are indeed due to uncertainty-guided exploration.\n\nLakshminarayanan, Balaji, Alexander Pritzel, and Charles Blundell. \"Simple and scalable predictive uncertainty estimation using deep ensembles.\" Advances in neural information processing systems 30 (2017).", "extra_scores": {}}, {"review_id": "QGIMwmPj1U", "reviewer": "Reviewer_up2F", "summary": "The data efficiency in alignment has been a long-term problem. To release the burden of human annotation, authors propose a novel active data selection process based on active contextual dueling bandit. The core of the algorithm is the contextual Borda function, which is estimated by kernelized ridge regression. Both context and one action are selected based on the Borda function. The former one is selected by uncertainty, and the latter one is selected by finding the argmax of upper confidence bounds. The authors also provided theoretical bounds as well as practical implementation for DPO. Results show that AE-Borda performs well on uniform sampling.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "* The research question is important and interesting\n* The method is overall sound\n* The method is novel\n* The authors release a new dataset which may be useful for further research.", "reasons_to_reject": "* The paper is a bit hard to understand as many terms are not explained very clearly, requiring readers to read extra materials outside of the paper. For example, the paper will be much clearer if the authors can explain RKHS and Li et al. (2023) mentioned in Line 153 more.\n\n* The experiment does not compare other active learning methods (like some mentioned in the Appendix). Therefore, it is unclear how well the method is in general sense.\n\n* During evaluation, authors compare two methods against a fixed answer, such as the SFT answer, and do not compare the two methods directly, which is more direct.", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fsGSGClQZ7", "reviewer": "Reviewer_1Thk", "summary": "This paper focuses on efficiently collecting human preference data for training large language models (LLMs). The problem is framed as an active contextual dueling bandit task, and the proposed algorithm is a new exploration algorithm that selectively chooses when and where to request preferences. Theoretical guarantees, including a polynomial worst-case regret bound, back the proposed approach.\n\nThe method is further extended to online and offline settings and is applied to preference alignment tasks using several LLMs across four datasets, including two new ones they introduce. The method outperforms baselines with fewer preference samples.\n\nOverall, this work makes a first move in this direction with both a practical and theoretical pursuit to improve data efficiency in preference-based learning for LLMs.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "- The related work coverage is comprehensive and navigates the technical contribution, in comparison to Dueling Bandits, Active Contextual Bandit Optimization, alternative contextual bandit methods, uncertainty estimation in large language models, and concurrent work on active data selection in LLMs.\n- A wide range of results (3 SFT models) and generalization ability are presented, providing sufficient evidence for the proposed method's success.\n- I'm not in a position to verify all the theoretical contributions supporting the arguments. However, the experiment design, presentations, and the story explaining the behavior of the proposed algorithm, e.g., Algorithm 1-2, Figure 2-5, and Figure 12, are easy to understand from a non-technical perspective and are much appreciated, in my opinion.", "reasons_to_reject": "- I find the arguments, evidences, presentation has high quality from a non-technical perspective.\n- I have no concern in the general quality, but in case there are technical problems in the theoretical part of this paper, the accept/rejection decisions should be carefully considered.", "questions_to_authors": "1. The propose algorithm leverages Contextual Borda Function for the active exploration procedure, there are always concerns in the efficiency of active exploration due to the existence of Condorcet winner and 'intransitivity' as described below, I wonder does the proposed method has any potential impact or connection to these sophistications?\n\nCondorcet paradox in aligning LLMs: (K. Liu, et al) https://arxiv.org/abs/2503.10990\n\nIntransitivity in preference dataset: (J. Duan, et al) https://arxiv.org/abs/2409.19325", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a theoretically grounded and practically motivated active learning method for sample-efficient preference alignment in LLMs, framed via a contextual dueling bandit formulation. It introduces novel Borda-based selection strategies and demonstrates consistent improvements over baselines on multiple datasets. The paper is generally well-written, and the authors have responded thoughtfully to reviewer concerns, including additional experiments. While comparisons to some recent related work were initially lacking, the rebuttal and added results sufficiently address this. Given the solid theoretical contributions, practical significance, and overall positive reviewer consensus (scores 6, 5, 8), I recommend Accept.
Decision: Accept