Preference learning and direct preference optimization

Let $Y$ be a finite nonempty set. A probability vector on $Y$ is a family $p=(p_y{)}_{y\in Y}$ with $p_y\ge 0$ and ${\sum }_{y\in Y}{p}_y=1$. For probability vectors $p,q$, define the finite relative entropy $D(p\mathrm{\parallel }q)={\sum }_{y:p_y>0}{p}_y\log \frac{p_y}{q_y}$ when $p_y=0$ whenever $q_y=0$, and define $D(p\mathrm{\parallel }q)=+\mathrm{\infty }$ otherwise. Terms with $p_y=0$ are omitted. Given a real reward $r:Y\to \mathbb{R}$ and a coefficient $\beta >0$, define $F_{q,r,\beta }(p)={\sum }_{y\in Y}{p}_{y}r(y)-\beta D(p\mathrm{\parallel }q)\mathrm{.}$ The finite KL-regularized policy-improvement problem is to maximize $F_{q,r,\beta }$ over all probability vectors $p$ on $Y$. The reference $q$ has full support when $q_y>0$ for every $y\in Y$; in that case $F_{q,r,\beta }(p)$ is finite for every $p$.

Finite KL divergence: uses the same directed finite sum, omits zero first-coordinate terms, and assigns $+\mathrm{\infty }$ when $p$ has positive mass where $q$ is zero.

Natural logarithm: defines $\log$ on $(0,\mathrm{\infty })$ as the inverse of the exponential function.

Let $X$ be a finite nonempty prompt set. For each $x\in X$, let $Y_x$ be a finite response set with at least two elements, and let $r_x:Y_x\to \mathbb{R}$ be a real-valued reward. The Bradley–Terry model assigns to each ordered pair of distinct responses $a,b\in Y_x$ the two-outcome comparison $a\succ b$ or $b\succ a$, with $\mathrm{Pr}(a\succ b\mid x)=\sigma (r_x(a)-r_x(b)),\sigma (t)=\frac{1}{1+e^{-t}}\mathrm{.}$ Here $a\succ b$ means that response $a$ is preferred to response $b$ at prompt $x$; the probability of the reverse outcome is $1-\mathrm{Pr}(a\succ b\mid x)=\sigma (r_x(b)-r_x(a))$. This is a statistical model for pairwise comparisons, not a universal law of human preference.

Binary logistic and multiclass softmax models: defines the same sigmoid $\sigma (t)=(1+e^{-t}{)}^{-1}$ for finite real $t$.

Rafailov et al., §3, Bradley–Terry preference model

Purdue PrefOpt course notes, §2, Bradley–Terry model

Let $Y$ be a finite nonempty set, let $q$ be a probability vector on $Y$ with $q_y>0$ for every $y$, let $r:Y\to \mathbb{R}$, and let $\beta >0$. Define $Z={\sum }_{y\in Y}{q}_y{e}^{r(y)\mathrm{/}\beta },p_y^{\ast }=\frac{q_y{e}^{r(y)\mathrm{/}\beta }}{Z}\mathrm{.}$ Then $Z$ is finite and positive, $p^{\ast }$ is a full-support probability vector, the maximum objective value is $F_{q,r,\beta }(p^{\ast })=\beta \log Z$, and for every probability vector $p$ on $Y$, $F_{q,r,\beta }(p^{\ast })-F_{q,r,\beta }(p)=\beta D(p\mathrm{\parallel }{p}^{\ast })\ge 0.$ Equality holds exactly when $p=p^{\ast }$. Thus $p^{\ast }$ is the unique maximizer of the finite KL-regularized policy-improvement objective.

Finite KL-regularized policy improvement: defines $F_{q,r,\beta }$ and the finite KL support convention.

Finite-label score loss: defines logarithmic loss as $-\log q_y$ and its expected loss as the corresponding finite sum.

Strict propriety of finite logarithmic loss: the truthful forecast uniquely minimizes expected logarithmic loss on the finite simplex.

For each prompt $x$ under consideration, let $Y_x$ be a finite response set with at least two elements, let $q_x$ be a probability vector with $q_x(y)>0$ for every $y\in Y_x$, let $r_x:Y_x\to \mathbb{R}$, and let $\beta >0$. Define $Z_x={\sum }_{y\in Y_x}{q}_x(y)e^{r_x(y)\mathrm{/}\beta }$ and $p_x^{\ast }(y)=q_x(y)e^{r_x(y)\mathrm{/}\beta }\mathrm{/}{Z}_x$. For every distinct $a,b\in Y_x$, $r_x(a)-r_x(b)=\beta \log \frac{p_x^{\ast }(a)}{q_x(a)}-\beta \log \frac{p_x^{\ast }(b)}{q_x(b)},$ so the Bradley–Terry probability is $\mathrm{Pr}(a\succ b\mid x)=\sigma \text{\hspace{0.17em}⁣}(\beta \log \frac{p_x^{\ast }(a)}{q_x(a)}-\beta \log \frac{p_x^{\ast }(b)}{q_x(b)})\mathrm{.}$ Conversely, every full-support probability vector ${\pi }_x$ on $Y_x$ is the unique Gibbs policy for reward ${\widehat{r}}_x(y)=\beta \log ({\pi }_x(y)\mathrm{/}{q}_x(y))$; adding any prompt-only constant $c_x$ to this reward leaves both the Gibbs policy and the Bradley–Terry probabilities unchanged.

Let $D=((x_i,y_i^w,y_i^l){)}_{i=1}^n$ be a finite ordered dataset with $n\ge 1$, $y_i^w,y_i^l\in Y_{x_i}$, and $y_i^w\mathrm{\ne }{y}_i^l$. Let $\mathrm{\Theta }\subseteq {\mathbb{R}}^d$ be open and let each conditional policy ${\pi }_{\theta }(\cdot \mid x_i)$ be a probability vector with ${\pi }_{\theta }(y\mid x_i)>0$ for every $y\in Y_{x_i}$, whose coordinates are continuously differentiable in $\theta \in \mathrm{\Theta }$. Put $u_i(\theta )=\beta (\log \frac{{\pi }_{\theta }(y_i^w\mid x_i)}{q_{x_i}(y_i^w)}-\log \frac{{\pi }_{\theta }(y_i^l\mid x_i)}{q_{x_i}(y_i^l)}),{\mathcal{L}}_D(\theta )=\frac{1}{n}{\sum }_{i=1}^n\log (1+e^{-u_i(\theta )})\mathrm{.}$ Then ${\mathcal{L}}_D$ is the finite direct preference optimization (DPO) loss: the average negative log likelihood for the Bradley–Terry model with implicit reward ${\widehat{r}}_{\theta }(x_i,y)=\beta \log \text{\hspace{0.17em}⁣}({\pi }_{\theta }(y\mid x_i)\mathrm{/}{q}_{x_i}(y))$. Its Euclidean gradient is ${\mathrm{\nabla }}_{\theta }{\mathcal{L}}_D(\theta )=-\frac{\beta }{n}{\sum }_{i=1}^n\sigma (-u_i(\theta ))({\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(y_i^w\mid x_i)-{\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(y_i^l\mid x_i))\mathrm{.}$ Here ${\mathrm{\nabla }}_{\theta }$ is the column vector of Euclidean partial derivatives on the open set $\mathrm{\Theta }$.

Finite Bradley–Terry preference model: defines $\mathrm{Pr}(a\succ b\mid x)=\sigma (r_x(a)-r_x(b))$ and the sigmoid.

Finite KL-regularized policy improvement: defines the finite KL objective and its reward/reference conventions.

Finite-action Gibbs policy theorem: gives the unique optimizer $p_x^{\ast }$ and its normalization.

Chain rule for total derivatives: differentiates the finite composition of the loss and the conditional log-probability coordinates.

Natural logarithm derivative: supplies $(\log t{)}^{\mathrm{\prime }}=1\mathrm{/}t$ for $t>0$.

Exponential derivative: supplies $(e^t{)}^{\mathrm{\prime }}=e^t$ for real $t$.

Rafailov et al., §4 Eqs. (6)–(7), Appendix A.2 and A.4

Purdue PrefOpt course notes, §§3e–4a

The Bradley–Terry equation is a modeling assumption for pairwise comparison noise, not a universal law of human preference. Here, model misspecification means that the actual pairwise conditional probabilities are not generated by any reward in this Bradley–Terry model. The Gibbs and direct preference optimization (DPO) formulas proved here use a finite response set, a full-support reference, and finite real rewards. For a countably infinite response space, the normalizing sum $Z={\sum }_y{q}_y{e}^{r(y)\mathrm{/}\beta }$ would have to be positive and finite, and the reward and KL sums would need convergence conditions that make them well-defined; no such extension is claimed.

For a fixed prompt, let $G=(Y,E)$ be the graph whose vertices are the finite responses and whose edges are the observed comparisons, with each edge joining the two responses compared. A connected component is a maximal subset of vertices in which every two vertices can be joined by a path of edges in $E$. If $G$ has connected components $C_1,\dots ,C_k$, adding a constant $c_j$ to every reward in $C_j$ leaves every observed edge difference unchanged because both endpoints of each edge lie in one component. Thus the Bradley–Terry probabilities on observed edges stay the same. But the Gibbs mass of component $C_j$ is $p^{\ast }(C_j)=\frac{{\sum }_{y\in C_j}{q}_y{e}^{r(y)\mathrm{/}\beta }}{{\sum }_{\mathrm{\ell }=1}^k{\sum }_{y\in C_{\mathrm{\ell }}}{q}_y{e}^{r(y)\mathrm{/}\beta }},$ so after the component shift its numerator and corresponding denominator contribution are multiplied by $e^{c_j\mathrm{/}\beta }$. With full-support $q$, distinct component shifts can therefore change the policy's relative mass across components without changing any observed comparison probability. Pairwise data on a disconnected graph alone do not identify that policy mass.

Here, identifying a policy from comparisons means uniquely determining it from the exact probabilities on the observed edges. The finite DPO loss and finite update procedure do not by themselves show that minimizing empirical loss recovers the true policy, that the parameterized family can represent that policy, that the learned policy performs well on new prompts or comparisons, or that the updates converge to a minimizer. Such claims require additional assumptions on the comparison sampling process, model class, and optimization behavior; none is supplied here.

Input a finite ordered preference dataset $D=((x_i,y_i^w,y_i^l){)}_{i=1}^n$ with $n\ge 1$, finite response sets $Y_{x_i}$ of size at least two, distinct $y_i^w,y_i^l\in Y_{x_i}$, reference probability vectors $q_{x_i}$ with all coordinates positive, a coefficient $\beta >0$, a parameter domain $\mathrm{\Theta }\subseteq {\mathbb{R}}^d$ that is open, and a conditional policy family ${\pi }_{\theta }(\cdot \mid x_i)$ that is a probability vector with all coordinates positive on each $Y_{x_i}$ for every $\theta \in \mathrm{\Theta }$, with coordinates totally differentiable in $\theta$ and continuous derivative. Also input an initial value ${\theta }_0\in \mathrm{\Theta }$, a finite integer $T\ge 0$, a list of finite nonempty mini-batches $B_t=(i_{t,1},\dots ,i_{t,m_t})$ with indices in $\{1,\dots ,n\}$ for each $0\le t<T$, and finite step sizes ${\eta }_t\ge 0$. Duplicated indices in a mini-batch are allowed. Require each observed scalar log-probability $\theta \mapsto \log {\pi }_{\theta }(y_i^w\mid x_i)$ and $\theta \mapsto \log {\pi }_{\theta }(y_i^l\mid x_i)$ to be represented by a finite real-arithmetic graph whose primitive maps are totally differentiable with continuous derivative matrices on an open neighborhood of every evaluated parameter; a piecewise-$C^1$ primitive is allowed only on a unique strict branch.

Also supply an exact membership oracle $M_{\mathrm{\Theta }}:{\mathbb{R}}^d\to \{0,1\}$ that returns $1$ exactly on $\mathrm{\Theta }$ and terminates on every call, with finite declared per-call cost $c_{\mathrm{\Theta }}(z)$. Use this oracle for the candidate-parameter test below. Supply terminating exact evaluators for the policy-graph primitive values, derivative-transpose applications, and primitive-domain and strict-branch tests. In the work model, each such primitive call and each scalar arithmetic operation, comparison, exponential, logarithm, maximum, or absolute value costs one unit; vector operations count their scalar entries. Membership-oracle calls are counted separately and their costs added. These supplied oracle operations are part of the input model; openness of $\mathrm{\Theta }$ alone is not asserted to provide a computable membership test, nor is a bit-complexity or floating-point bound asserted.

For real $u$, evaluate the per-record loss by the equivalent stable expression $s(u)=\max (0,-u)+\log (1+e^{-\mathrm{\mid }u\mathrm{\mid }})=\log (1+e^{-u})\mathrm{.}$ Set $u_i(\theta )=\beta [\log ({\pi }_{\theta }(y_i^w\mid x_i)\mathrm{/}{q}_{x_i}(y_i^w))-\log ({\pi }_{\theta }(y_i^l\mid x_i)\mathrm{/}{q}_{x_i}(y_i^l))]$ and initially compute $L_D({\theta }_0)=n^{-1}{\sum }_{i}s(u_i({\theta }_0))$. Store $({\theta }_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}},L_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})=({\theta }_0,L_D({\theta }_0))$.

For $t=0,\dots ,T-1$, compute the mini-batch objective $L_t(\theta )=m_t^{-1}{\sum }_{j=1}^{m_t}s(u_{i_{t,j}}(\theta ))$. For each index in the batch, use reverse-mode AD on the finite policy-log-probability graphs to compute the Euclidean gradients of the two log probabilities, and form the exact loss gradient from the finite DPO gradient formula proved on the A page: $g_t=-\frac{\beta }{m_t}{\sum }_{j=1}^{m_t}\sigma (-u_{i_{t,j}}({\theta }_t))({\mathrm{\nabla }}_{\theta }\log {\pi }_{{\theta }_t}(y_{i_{t,j}}^w\mid x_{i_{t,j}})-{\mathrm{\nabla }}_{\theta }\log {\pi }_{{\theta }_t}(y_{i_{t,j}}^l\mid x_{i_{t,j}}))\mathrm{.}$ Do not differentiate through the max/absolute-value expression used only to evaluate $s(u)$; use this explicit derivative formula. If reverse mode returns DOMAIN_ERROR or NONDIFFERENTIABLE, stop and return $({\theta }_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}},L_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})$ with that status. Otherwise set ${\theta }^{\mathrm{\prime }}={\theta }_t-{\eta }_t{g}_t$. Evaluate $M_{\mathrm{\Theta }}({\theta }^{\mathrm{\prime }})$. If its value is $0$, so ${\theta }^{\mathrm{\prime }}\mathrm{\notin }\mathrm{\Theta }$, stop and return the last valid pair with status DOMAIN_ERROR. If its value is $1$, so ${\theta }^{\mathrm{\prime }}\in \mathrm{\Theta }$, set ${\theta }_{t+1}={\theta }^{\mathrm{\prime }}$, evaluate $L_D({\theta }_{t+1})$, and update $({\theta }_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}},L_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})=({\theta }_{t+1},L_D({\theta }_{t+1}))$.

After all $T$ updates, return $({\theta }_T,L_D({\theta }_T))$ with status COMPLETED. Thus $T=0$ returns the initial parameters and initial full-data loss. The procedure uses the fixed mini-batch indices and step-size schedule as supplied; it makes no convergence or statistical-optimality assertion.

Finite-budget DPO preserves its valid pair and terminates with finite oracle work ↗: proves well-definedness, the stored valid-pair invariant, the exact mini-batch gradient, finite termination, and the work and membership-oracle bounds under the declared input model.

Finite Bradley–Terry preference model: defines the pairwise comparison probability and sigmoid.

DPO reward-policy reparameterization and gradient: supplies the exact finite DPO loss gradient.

Finite real-arithmetic program: fixes the finite topological graph and real-arithmetic conventions, and allows a primitive to be piecewise C1 only on a unique strict branch.

Continuously differentiable Euclidean maps: C1 means total differentiability with continuous derivative matrix.

Reverse-mode automatic differentiation: specifies the reverse sweep for a finite scalar-output C1 graph.

Reverse mode computes the graph gradient: confirms the returned cotangents are the exact derivative on each fixed strict branch.

Rafailov et al., §4 Eq. (7), Appendix B implementation

Purdue PrefOpt course notes, §4a

This is a finite real-arithmetic update procedure. The equivalent loss-value expression and procedure properties are justified by the separate result listed above. The gradient is computed from the explicit smooth formula, so the max/absolute-value implementation branch at $u=0$ is not differentiated. No floating-point error bound, minimizer attainment, convergence rate, or generalization guarantee is asserted.

For every input of the finite-budget DPO procedure, under its supplied exact evaluator and membership-oracle model, all prescribed loss evaluations are finite and every successful reverse sweep gives the exact stated mini-batch gradient. Throughout the run, the stored pair is $(\theta ,L_D(\theta ))$ for the most recently accepted parameter $\theta \in \mathrm{\Theta }$; initially this is $({\theta }_0,L_D({\theta }_0))$. In particular, rejected candidates are not used for policy evaluation. The procedure terminates after at most $T$ attempted updates and returns this valid pair with the prescribed diagnostic status on early exit, or $({\theta }_T,L_D({\theta }_T))$ with status COMPLETED when all $T$ updates are accepted. When $T=0$, it returns the initial pair with status COMPLETED.

Put $M={\sum }_{t=0}^{T-1}{m}_t$, with $M=0$ for $T=0$. There is a finite constant $C\ge d+1$, determined by the finitely many supplied log-probability graphs, their fixed node dimensions and the unit-cost primitive model, such that the work excluding parameter-domain membership is

The implicit constant is independent of the numerical parameters and step sizes. There are at most $T$ calls to $M_{\mathrm{\Theta }}$. For the actual queried candidates $z_1,\dots ,z_Q$, the membership cost is ${\sum }_{j=1}^Q{c}_{\mathrm{\Theta }}(z_j)<\mathrm{\infty }$, with $Q\le T$, and is added to the displayed work. If a uniform finite membership bound $C_{\mathrm{\Theta }}$ is supplied, this contribution is at most $T{C}_{\mathrm{\Theta }}$. These are bounds in the declared exact primitive/oracle model, not a universal algorithm for membership in arbitrary open sets. No convergence, descent, or statistical-optimality conclusion is asserted.

Finite-budget direct preference optimization by mini-batch gradient descent: gives the full input scope, exact oracle model, accept/reject rule and returned pair.