2  Learning

Intended Learning Outcomes

By the end of this chapter you will be able to:

• Identify appropriate train/test splitting strategies for preference data and understand their implications for model evaluation.
• Implement maximum likelihood estimation via gradient descent for the Bradley-Terry model, deriving and computing gradients efficiently.
• Apply Bayesian inference using Markov Chain Monte Carlo (MCMC) to quantify parameter uncertainty and obtain posterior distributions.
• Apply Laplace approximation to perform inference for Gaussian Process preference models, understanding why non-Gaussian likelihoods require approximation.
• Derive online learning algorithms (Elo ratings) as stochastic gradient ascent and explain when online methods are preferred over batch learning.
• Compare batch maximum likelihood, Bayesian inference, and online learning approaches in terms of computational cost, statistical efficiency, and practical applicability.
• Evaluate learned preference models using multiple metrics including AUC, log-likelihood, and calibration error.
• Apply regularization techniques (L2 penalty, early stopping) to prevent overfitting and improve generalization.
• Conduct k-fold cross-validation for model selection and hyperparameter tuning in preference learning settings.
• Implement modern optimization methods (Adam, learning rate schedules) and diagnose convergence through loss curves and gradient norms.
• Analyze real-world preference data from language model alignment, addressing practical challenges such as noise, sparsity, and cold-start problems.

Suggested Lecture Plan

This chapter can be covered in two 50-minute lectures plus a hands-on lab session:

Lecture 1 (Sections 3.1–3.4): Core parameter estimation methods

• Train/test splitting and evaluation metrics (10 min)
• Maximum likelihood estimation for Bradley-Terry: derivation, implementation, evaluation (20 min)
• Bayesian inference with MCMC: posterior distributions, Metropolis-Hastings (15 min)
• Comparison of MLE vs Bayesian approaches (5 min)

Lecture 2 (Sections 3.5–3.8): Advanced learning topics

• Online learning with Elo ratings: derivation as SGD, applications (15 min)
• Regularization and overfitting: L2 penalty, validation curves (15 min)
• Cross-validation and model selection (10 min)
• Optimization methods: GD vs Adam, learning rate schedules (10 min)

Lab session: Real-world application and exercises

• Apply methods to LLM preference data (30 min)
• Work on selected exercises (20 min)

Designing a good reward signal by hand for a complex AI system is difficult and error-prone. Instead of manually specifying desirable behavior, we can learn a utility signal from preference data. In this chapter, we explore how to infer an underlying utility from various forms of feedback. Throughout, we include mathematical formulations and code examples to illustrate the learning process.

2.1 Chapter Overview

Section 1.6 in Chapter 2 established the foundational models for preference data: the Rasch model for item-wise responses, the Bradley-Terry model for pairwise comparisons, and K-dimensional factor models for richer representations. We saw how these models formalize the relationship between latent parameters and observed choices.

This chapter addresses the central question of learning: given observed preference data, how do we estimate the parameters of these models? We explore four complementary perspectives on parameter learning, each with distinct advantages:

• Maximum Likelihood Estimation (Section 2.3): Find parameters that maximize the probability of observed data. Fast and scalable, but provides only point estimates.
• Bayesian Inference (Section 2.4, Section 2.4.2): Treat parameters as random variables with prior distributions. We cover both parametric models (using MCMC) and nonparametric Gaussian Process models (using Laplace approximation). Quantifies uncertainty but requires more computation.
• Online Learning (Section 2.5): Update estimates incrementally as new data arrives. Essential for dynamic systems with continuously arriving feedback.

Beyond these core methods, we cover essential machine learning techniques for practical applications:

• Regularization (Section 2.6): Prevent overfitting through L2 penalties and early stopping.
• Model Selection (Section 2.7): Use cross-validation to tune hyperparameters and compare approaches.
• Optimization (Section 2.8): Improve convergence with modern methods like Adam and adaptive learning rates.
• Real-World Application (Section 2.9): Apply all methods to language model preference data, confronting practical challenges.

Chapters 4-6 will build on these learning foundations to address active data collection (Chapter 4), decision-making under learned preferences (Chapter 5), and heterogeneous populations (Chapter 6).

2.2 Learning from Preference Data

Section 1.6 introduced the latent variable models for preference data: the Rasch model for item-wise responses, K-dimensional factor models (including the logistic factor model and the ideal point model), and the Bradley-Terry model for pairwise comparisons. We saw how these models relate user parameters \(U_i\) and item parameters \(V_j\) to observed responses, and how pairwise models can be derived from item-wise models.

This chapter focuses on learning the parameters of these models from observed data. We cover three complementary approaches:

1. Maximum Likelihood Estimation for Bradley-Terry and Rasch models — finding parameters that maximize the probability of the observed data
2. Bayesian Inference for uncertainty quantification — treating parameters as random variables with prior distributions
3. Online Learning with the Elo rating system — updating parameter estimates incrementally as new data arrives

We begin by discussing how to split preference data into training and test sets, then develop estimation procedures for each approach.

2.3 Maximum Likelihood Estimation

Given a response from a particular generating process, there are various standard statistical inference procedures, such as maximum likelihood, maximum marginal likelihood, or Bayesian inference. These procedures are designed to infer parameters that are generalizable to new datasets. Hence, we discuss the training and testing dataset next.

The simplest train/test splitting is random, where we select a random subset (e.g., 80%) of the response matrix to be in the training set, and the rest in the test set. We can demonstrate, for example, with the Bradley-Terry response with 80% training and 20% testing data:

Having the train and test datasets from the Bradley–Terry response, which are denoted as \(\mathcal{D}_{\text{train}}\) and \(\mathcal{D}_{\text{test}}\), we first demonstrate the parameter learning with full information maximum likelihood estimation on a single user:

\[ \hat{V} = \arg\max_{V} \sum_{j,j' \in \mathcal{D}_{\text{train}}} \log p(Y_{0,jj'} | \sigma(H_{0,jj'})), \quad H_{0} = V 1_M^\top - 1_M V^\top, \tag{2.1}\] where \(1_M\) is a column vector of 1 with length \(M\) and \(H_{0,jj'} = v_j-v_{j'}\) for a fixed user \(0\). The optimization can be carried out with standard optimizers, such as gradient descent.

Assumption: Connected Comparison Graph

The MLE for Bradley-Terry parameters exists and is unique if and only if the comparison graph is strongly connected—that is, for every pair of items \((j, k)\), there exists a chain of comparisons linking \(j\) to \(k\) (see Ford Jr 1957). If some items have never been compared (directly or transitively), their utility parameters are not identifiable and the MLE diverges to \(\pm\infty\). In practice, sparse datasets (e.g., LLM evaluation where each response pair is annotated only once) frequently produce disconnected comparison graphs. Regularization (Section 2.6) addresses this by shrinking all parameters toward zero, effectively imposing a prior that prevents divergence.

Let \(\mathcal{N}_m^+ = \{(m,k) \in \mathcal{D}_{\text{train}}\}\) be pairs recorded in the order \((m,k)\). Let \(\mathcal{N}_m^- = \{(k,m) \in \mathcal{D}_{\text{train}}\}\) be pairs recorded in the order \((k,m)\). Define residuals \(r_{mk} = y_{mk} - \sigma(V_m - V_k)\) and \(r_{km} = y_{km} - \sigma(V_k-V_m)\). Then

\[ \frac{\partial \ell}{\partial V_m} = \sum_{(m,k)\in \mathcal{N}^+_m} r_{mk} - \sum_{(k,m)\in \mathcal{N}^-_m} r_{km}. \tag{2.2}\]

This shows the contribution of data about \(m\) only. Each comparison with opponent \(k\) adds a term equal to the observed-minus-predicted win indicator, with a plus sign if \(m\) is listed first and a minus sign if \(m\) is listed second. Intuitively, if \(m\) beats \(k\) more often than the model predicts, the residual is positive and the gradient pushes \(V_m\) up. If \(m\) loses to \(k\) more than predicted, the residual is negative and the gradient pushes \(V_m\) down.

In this synthetic setting, one way to interpret the result is to compare with the Bayes optimal AUC. Here we quantify an upper bound on achievable test AUC under the assumed data-generating process. For each test pair \((j,k)\) we know the ground-truth win probability \(P_{jk}=\sigma(V_j-V_k)\) from the simulator. The Bayes-optimal score for that pair is exactly this probability, \(s^*_{jk}=P_{jk}\). Any classifier that ranks pairs by \(s^*\) maximizes AUC in expectation because it orders pairs by their true success probabilities. To estimate the corresponding Bayes AUC on our finite test set, we keep the same index set of pairs and repeatedly resample binary labels \(Y_{jk} \sim \mathrm{Bern}(P_{jk})\), then compute \(\mathrm{AUC}(s^*, Y)\) on each resample using a tie-aware definition. The mean of these Monte Carlo AUCs is the Bayes-optimal test AUC, and the empirical quantiles give a sampling range induced purely by label noise. For comparison, we compute the model’s AUC by replacing \(s^*_{jk}\) with the learned scores \(s^{*\text{model}}_{jk}=\sigma(\hat V_j-\hat V_k)\). The gap between the two summarizes how far the fitted model is from the oracle ranking implied by the true \(P^*_{jk}\) on the exact same test pairs.

The result shows that the inference has found a good solution compared to the Bayes optimal estimator! An additional, natural test is to see if the estimated parameters match the true ones. Since the likelihood function only pays attention to the difference of item appeal for any pair, the appeal is only identifiable up to a shift and scale transform. The standard practice is to center and whiten the solution.

Looking Ahead: Regularization

MLE can overfit when parameters outnumber observations. Section 2.6 introduces L2 regularization, which adds a penalty \(\frac{\lambda}{2}\|V\|_2^2\) to the objective. This is equivalent to MAP estimation with a Gaussian prior—connecting MLE to the Bayesian framework we develop next.

2.4 Bayesian Inference

A Bayesian approach provides a natural alternative to maximum likelihood for parameter estimation. Instead of finding a single point estimate, we place a prior distribution on parameters and update it using the likelihood from observed comparisons. This yields a posterior distribution that captures both central estimates and the uncertainty around them. We first cover parametric models using MCMC, then extend to nonparametric Gaussian Process models using Laplace approximation.

2.4.1 Parametric Models

For the Bradley–Terry model with finite-dimensional item parameters \(V\), we place i.i.d. standard normal priors and update them using the Bernoulli likelihood from observed comparisons. In practice, this posterior cannot be computed in closed form, so we turn to Markov chain Monte Carlo (MCMC), which constructs a sequence of samples that, in the limit, follow the posterior distribution.

The Metropolis–Hastings (MH) algorithm is straightforward to apply: at each step, we propose a new value for one or more coordinates of (V) (e.g., from a Gaussian centered at the current state), compute the acceptance ratio as the ratio of posterior densities between the proposed and current states, and accept the proposal with that probability. Repeating this process produces a chain of samples that can be used to approximate posterior means, variances, or other functionals of interest. This approach not only yields point predictions but also quantifies uncertainty about the relative strengths of items under the Bradley–Terry model.

Let the prior be i.i.d. standard normal for each item parameter: \(p(V) = \prod_{j=1}^M \mathcal N(V_j \mid 0, 1)\). Then the posterior distribution is \(p(V \mid \mathcal D) = p(\mathcal D \mid V)p(V)/p(\mathcal D),\) where the likelihood is \[ p(\mathcal D \mid V) = \prod_{(j,j')\in\mathcal I} \sigma(V_j - V_{j'})^{Y_{jj'}} \bigl(1-\sigma(V_j - V_{j'})\bigr)^{1-Y_{jj'}}. \tag{2.3}\]

The denominator is the marginal likelihood (evidence), which is intractable in closed form, so we resort to MCMC (e.g., MH) to sample from the posterior. Suppose we are at current (parameter) state \(V^{(t)}\). We propose a new state \(V'\) from a proposal distribution, such as Gaussian: \(q(V' \mid V^{(t)}) = \mathcal N (V'; V^{(t)}, \tau^2 I),\) where \(\tau^2\) is a step-size variance. This proposal is symmetric, meaning \(q(V' \mid V^{(t)}) = q(V^{(t)} \mid V').\) For any proposal distribution \(q(V' \mid V^{(t)})\), the Metropolis–Hastings acceptance probability is

\[ \alpha = \min \left\{1, \frac{p(V' \mid \mathcal D) \cdot q(V^{(t)} \mid V')}{p(V^{(t)} \mid \mathcal D) \cdot q(V' \mid V^{(t)})}\right\}. \tag{2.4}\]

This says: accept the proposal with probability proportional to how much more plausible it is under the posterior, adjusted by how easy it is to propose back. If we choose a Gaussian proposal, the proposal terms cancel out in the ratio due to symmetry. So the acceptance rule simplifies to \[ \alpha = \min \left\{1, \frac{p(V' \mid \mathcal D)}{p(V^{(t)} \mid \mathcal D)}\right\} = \min \left\{1, \frac{p(\mathcal D \mid V') \cdot p(V')}{p(\mathcal D \mid V^{(t)}) \cdot p(V^{(t)})}\right\}. \tag{2.5}\]

Assumption: MCMC Has Converged

Metropolis-Hastings produces samples from the posterior asymptotically, but in finite time, the chain may not have converged. A reasonable acceptance rate (20–50%) is necessary but not sufficient: the chain may mix slowly between modes or explore only a local region of the posterior. In practice, one should run multiple independent chains from dispersed starting points and check convergence using diagnostics such as the Gelman-Rubin \(\hat{R}\) statistic (which should be close to 1.0) and effective sample size. The Laplace approximation introduced below avoids sampling entirely but assumes the posterior is unimodal and approximately Gaussian—an assumption that fails when data is sparse or the posterior is multimodal.

2.4.2 Gaussian Processes

MCMC works well for finite-dimensional parameter vectors, but what if we want to learn a nonparametric reward function? Gaussian Processes (GPs) extend Bayesian inference to function spaces, placing a prior distribution over reward functions \(r \sim \mathcal{GP}(m, k)\) and combining it with the Bradley-Terry likelihood for preferences. The challenge is that this likelihood is non-Gaussian, breaking the standard GP posterior formulas and requiring approximations like Laplace.

The inference problem. Given pairwise comparisons \(\mathcal{D} = \{(x_A^{(i)}, x_B^{(i)}, y_i)\}_{i=1}^n\) where \(y_i = 1\) if item \(A\) was preferred, we want to compute the posterior: \[ p(r \mid \mathcal{D}) \propto p(\mathcal{D} \mid r) \cdot p(r) \tag{2.6}\]

The likelihood follows the Bradley-Terry model: \[ p(y_i = 1 \mid r) = \sigma\left(r(x_A^{(i)}) - r(x_B^{(i)})\right) \tag{2.7}\]

Because this sigmoid likelihood is not Gaussian, the posterior \(p(r \mid \mathcal{D})\) is no longer a Gaussian Process.

2.4.2.1 Laplace Approximation

The Laplace approximation provides a tractable Gaussian approximation to the true posterior:

1. Find the posterior mode \(\mathbf{r}^* = \arg\max_{\mathbf{r}} \log p(\mathcal{D} \mid \mathbf{r}) + \log p(\mathbf{r})\)
2. Approximate with a Gaussian centered at the mode, using the Hessian of the log-posterior as precision

For preference data with GP prior (zero mean), the mode satisfies: \[ \mathbf{r}^* = \arg\max_{\mathbf{r}} \sum_{i=1}^n \log \sigma\left(y_i (r(x_A^{(i)}) - r(x_B^{(i)}))\right) - \frac{1}{2}\mathbf{r}^\top K^{-1} \mathbf{r} \tag{2.8}\]

where \(K\) is the kernel matrix and \(\mathbf{r} = [r(x_1), \ldots, r(x_m)]^\top\) collects function values at all unique points appearing in comparisons.

Newton’s method for finding the mode. The gradient and Hessian of the log-posterior are: \[ \nabla_{\mathbf{r}} \log p(\mathbf{r} \mid \mathcal{D}) = \mathbf{g} - K^{-1}\mathbf{r} \tag{2.9}\] \[ \nabla^2_{\mathbf{r}} \log p(\mathbf{r} \mid \mathcal{D}) = -W - K^{-1} \tag{2.10}\]

where \(\mathbf{g}\) is the gradient of the log-likelihood and \(W\) is a diagonal matrix with entries \(W_{ii} = p_i(1 - p_i)\) for predictions \(p_i = \sigma(r(x_A^{(i)}) - r(x_B^{(i)}))\).

The approximate posterior. After finding \(\mathbf{r}^*\), the Laplace approximation gives: \[ p(\mathbf{r} \mid \mathcal{D}) \approx \mathcal{N}\left(\mathbf{r}^*, (K^{-1} + W)^{-1}\right) \tag{2.11}\]

This is structurally similar to standard GP regression, but with the data-dependent precision matrix \(W\) arising from the Bradley-Terry likelihood rather than observation noise.

Limitations of the Laplace Approximation

The Laplace approximation replaces the true posterior with a Gaussian centered at the MAP estimate \(\mathbf{r}^*\). This approximation can be poor when: (1) the posterior is multimodal (e.g., when items form disconnected clusters with few cross-cluster comparisons), (2) the MAP is near a boundary of the parameter space, or (3) there are very few comparisons so the likelihood barely constrains the posterior. In these settings, the Gaussian approximation underestimates posterior uncertainty and can produce overconfident predictions. Alternatives include expectation propagation (EP), which approximates each likelihood factor separately, or full MCMC sampling as described above.

2.4.2.2 Connection to Fisher Information

The Laplace approximation has a natural connection to the Fisher information framework we developed for linear models. The Hessian of the negative log-likelihood at the mode gives the observed Fisher information: \[ I_{\text{obs}} = W = \text{diag}(p_1(1-p_1), \ldots, p_n(1-p_n)) \tag{2.12}\]

Just as with linear preference models, comparisons with \(p \approx 0.5\) contribute the most information (highest \(p(1-p)\)), while “easy” comparisons where one option clearly dominates contribute little.

2.4.2.3 Computational Considerations

Complexity. Each Newton iteration requires \(O(m^3)\) computation for the matrix solve, where \(m\) is the number of unique points. For \(n\) comparisons involving \(m \leq 2n\) unique points, the total cost is \(O(n^3)\) per iteration.

Scalability. For large datasets, several approximations are available: - Inducing points: Approximate the GP using \(k \ll m\) pseudo-inputs, reducing complexity to \(O(k^2 n)\) - Variational inference: Optimize a lower bound on the marginal likelihood - Conjugate gradient methods: Avoid explicit matrix inversion

Hyperparameter learning. The kernel hyperparameters (length-scale \(\ell\), signal variance \(\sigma_f^2\)) can be learned by maximizing the Laplace-approximated marginal likelihood: \[ \log p(\mathcal{D} \mid \theta) \approx \log p(\mathcal{D} \mid \mathbf{r}^*) + \log p(\mathbf{r}^* \mid \theta) + \frac{1}{2}\log |K^{-1} + W|^{-1} \tag{2.13}\]

In Chapter 4, we will see how the GP posterior uncertainty enables active query selection—choosing which comparisons to ask to learn most efficiently.

2.5 Online Learning

In many applications, comparisons between items arrive sequentially over time rather than being observed all at once. For example, players in online games are continuously matched, or recommendation systems log one user preference at a time. In such settings, it is often computationally infeasible to refit the full Bradley–Terry model by maximum likelihood or MCMC after each new observation. Instead, we want an online update rule that adjusts item strengths incrementally as new outcomes arrive.

This is precisely the motivation behind the Elo rating system, originally introduced for ranking chess players and later widely adopted in competitive games, online platforms, and even information retrieval. The key idea is to maintain a current estimate of each item’s (or player’s) latent strength, and update only the two items involved in a match when a new result comes in.

The Elo rule can be derived as a stochastic gradient ascent method on the Bradley–Terry log-likelihood. Suppose item \(j\) plays against item \(j'\). Given the current parameters, the log-likelihood gradient with respect to \(V_j\) and \(V_{j'}\) is \[ \frac{\partial \ell}{\partial V_j} = (y - p), \qquad \frac{\partial \ell}{\partial V_{j'}} = -(y - p). \tag{2.14}\]

A stochastic gradient ascent step with learning rate \(\eta\) gives the update: \[ V_j \leftarrow V_j + \eta (y - p), \qquad V_{j'} \leftarrow V_{j'} - \eta (y - p). \tag{2.15}\]

This is exactly the Elo update rule. The learning rate \(\eta\) is often called the K-factor in Elo literature. If \(y=1\) (item \(j\) wins) but the model predicted a low \(p\), then \((y - p)\) is positive and \(V_j\) increases, \(V_{j'}\) decreases — the system learns that \(j\) is stronger than previously believed. If \(y=0\) (item \(j'\) wins), the opposite adjustment happens. The magnitude of the update is larger when the outcome is surprising (large prediction error), and smaller when the outcome is expected (small prediction error). Thus, Elo is an online learning algorithm for the Bradley–Terry model, interpretable as stochastic gradient ascent with a fixed step size.

Worked Example: Elo as Stochastic Gradient Ascent

Two chess players have current ratings \(V_A = 1500\) and \(V_B = 1700\) (using the traditional Elo scale where \(\sigma\) operates on \((V_A - V_B)/400\)). With \(K = 32\):

Step 1. Predicted win probability for A: \[p = \sigma\left(\frac{V_A - V_B}{400}\right) = \sigma\left(\frac{-200}{400}\right) = \sigma(-0.5) \approx 0.378\] Player A is expected to win about 38% of the time.

Step 2. Suppose A wins (upset!). The prediction error is \(y - p = 1 - 0.378 = 0.622\). Updates: \[V_A \leftarrow 1500 + 32 \times 0.622 = 1500 + 19.9 \approx 1520\] \[V_B \leftarrow 1700 - 32 \times 0.622 = 1700 - 19.9 \approx 1680\]

Step 3. If instead the favorite B had won (\(y = 0\), prediction error \(= -0.378\)): \[V_A \leftarrow 1500 - 32 \times 0.378 \approx 1488\] \[V_B \leftarrow 1700 + 32 \times 0.378 \approx 1712\]

Key insight: Upsets produce larger rating changes (19.9 points) than expected outcomes (12.1 points). This is exactly stochastic gradient ascent: the step size is proportional to the prediction error, so surprising results move parameters more. The \(K\)-factor controls the tradeoff between responsiveness (large \(K\)) and stability (small \(K\)).

Limitations of Fixed K-Factor Elo

The Elo system with a constant \(K\)-factor has several limitations. First, it weights all comparisons equally regardless of recency—there is no discounting of old information, so it cannot optimally track non-stationary preferences (e.g., an LLM improving through training). Second, a single \(K\) must trade off responsiveness against stability for all items, even though some items’ utilities may be well-established while others are new. Third, unlike Bayesian methods, Elo provides no uncertainty quantification—the rating \(V_j\) is a point estimate with no associated confidence interval. Systems like Glicko address some of these issues by maintaining per-item uncertainty estimates that decay with inactivity and scale the update magnitude accordingly.

2.6 Regularization and Overfitting

The maximum likelihood estimator maximizes fit to observed training data but may overfit, especially when the number of parameters is large relative to the amount of data. In preference learning, overfitting manifests as learned item parameters that capture noise in the training comparisons rather than true relative strengths. Regularization techniques penalize model complexity to improve generalization to held-out test data.

2.6.1 L2 Regularization

The most common regularization approach adds an L2 penalty term to the log-likelihood. For the Bradley-Terry model, the regularized objective becomes: \[ \mathcal{L}_{\text{reg}}(V) = \sum_{(j,j') \in \mathcal{D}_{\text{train}}} \log p(Y_{jj'} \mid V_j - V_{j'}) - \frac{\lambda}{2} \|V\|_2^2 \tag{2.16}\] where \(\lambda \geq 0\) is the regularization strength. The penalty \(\frac{\lambda}{2} \|V\|_2^2 = \frac{\lambda}{2} \sum_{j=1}^M V_j^2\) discourages large parameter values. When \(\lambda = 0\), we recover standard MLE. As \(\lambda\) increases, parameters shrink toward zero.

The regularized gradient adds a simple term to the MLE gradient: \[ \frac{\partial \mathcal{L}_{\text{reg}}}{\partial V_m} = \sum_{(m,k)\in \mathcal{N}^+_m} r_{mk} - \sum_{(k,m)\in \mathcal{N}^-_m} r_{km} - \lambda V_m \tag{2.17}\]

Intuitively, regularization creates a bias-variance tradeoff: small \(\lambda\) permits complex fits (low bias, high variance), while large \(\lambda\) enforces simpler models (high bias, low variance). The optimal \(\lambda\) balances these to minimize test error.

Connection to Bayesian Inference

L2 regularization corresponds exactly to maximum a posteriori (MAP) estimation with a Gaussian prior \(p(V_j) = \mathcal{N}(0, 1/\lambda)\). The regularization strength \(\lambda\) is the inverse prior variance: strong regularization (large \(\lambda\)) means a tight prior belief that parameters are near zero.

The validation curve demonstrates the regularization trade-off: at \(\lambda = 0\) (no regularization), the model overfits to training data, achieving high training AUC but lower test AUC. As \(\lambda\) increases, test performance improves until an optimal point, after which excessive regularization underfits. The gap between training and test AUC narrows with proper regularization, indicating better generalization.

2.6.2 Early Stopping

An alternative to explicit regularization is early stopping: monitor validation performance during training and stop when it begins to degrade, even if training performance continues improving. This exploits the empirical observation that gradient descent follows a path from simple to complex models.

Early stopping automatically selects model complexity through the training trajectory. Unlike L2 regularization, it requires no tuning of \(\lambda\), but does require held-out validation data to monitor.

Key Takeaway: When to Regularize

Regularization is most critical when:

• Few observations relative to parameters (e.g., 50 comparisons, 20 items)
• Imbalanced data: Some items have many comparisons, others have few
• High noise: Label noise or measurement error in comparisons

For large datasets with many comparisons per item, overfitting is less of a concern and regularization may have minimal impact. Always use validation data or cross-validation to tune regularization strength.

2.7 Model Selection and Cross-Validation

A single train/test split provides one estimate of generalization performance, but this estimate has high variance: a different random split may yield different results. Cross-validation (CV) systematically evaluates multiple train/test splits to obtain more reliable performance estimates and enable principled model selection.

2.7.1 K-Fold Cross-Validation

In k-fold cross-validation, we partition the data into \(k\) equally-sized folds. For each fold \(i \in \{1, \ldots, k\}\):

1. Train the model on all folds except fold \(i\)
2. Evaluate on fold \(i\) (held-out validation)
3. Record the validation metric (e.g., AUC, log-likelihood)

The final CV score is the average across all \(k\) folds: \(\text{CV}_k = \frac{1}{k} \sum_{i=1}^k \text{metric}_i\). The standard error quantifies uncertainty in the estimate.

For preference data, we partition the set of observed pairwise comparisons (not items) into folds, ensuring each fold contains a representative sample of comparisons.

The CV estimate of {cv_scores.mean():.4f} ± {cv_scores.std():.4f} is more reliable than a single train/test split. The standard deviation quantifies variability across folds.

2.7.2 Hyperparameter Tuning with Cross-Validation

Cross-validation enables principled hyperparameter selection: evaluate each candidate hyperparameter on CV performance and select the best. For Bradley-Terry, key hyperparameters include regularization strength \(\lambda\) and learning rate.

The error bars show the standard deviation across folds, indicating uncertainty in the CV estimate for each hyperparameter. Select the hyperparameter with highest mean CV performance.

2.7.3 Beyond AUC: Multiple Evaluation Metrics

AUC measures ranking quality but does not capture all aspects of model performance. Additional metrics provide complementary insights:

Log-Likelihood: Measures the probability the model assigns to observed outcomes. Higher is better. \[ \text{LL} = \sum_{(j,j') \in \mathcal{D}_{\text{test}}} \left[ Y_{jj'} \log \sigma(V_j - V_{j'}) + (1 - Y_{jj'}) \log (1 - \sigma(V_j - V_{j'})) \right] \tag{2.18}\]

Calibration Error: Measures whether predicted probabilities match empirical frequencies. Bin predictions into intervals (e.g., [0.0, 0.1), [0.1, 0.2), …) and compare average predicted probability to observed frequency in each bin.

Different metrics may favor different models. AUC focuses on ranking, log-likelihood on probability estimates, and calibration on frequency matching. Use multiple metrics to gain a comprehensive view of model quality.

Key Takeaway: Cross-Validation Best Practices

• Use CV for hyperparameter tuning, not test set evaluation (avoid overfitting to the test set)
• Report mean ± std across folds to quantify uncertainty
• Stratified splitting: For imbalanced data, ensure each fold has representative class proportions
• Temporal splitting: For sequential data (e.g., chess games over time), use time-based splits instead of random CV to avoid leaking future information into past predictions
• Nested CV: For unbiased performance estimates, use outer CV loop for evaluation and inner CV loop for hyperparameter selection

2.8 Optimization Methods

Gradient descent is the foundation for learning Bradley-Terry parameters, but modern optimization methods can accelerate convergence and improve final performance. We compare three widely-used optimizers and discuss when each is appropriate.

2.8.1 Beyond Vanilla Gradient Descent

Standard gradient descent updates parameters with a fixed learning rate: \(V \leftarrow V + \eta \nabla \mathcal{L}(V)\). This has two limitations:

1. Fixed step size: Large \(\eta\) causes instability; small \(\eta\) slows convergence
2. No momentum: Each step ignores the optimization history

Modern optimizers address these issues through adaptive learning rates and momentum.

2.8.2 Adam Optimizer

Adam (Adaptive Moment Estimation) maintains running averages of both gradients and squared gradients, adapting the learning rate per parameter. The update rule is:

\[ \begin{aligned} m_t &\leftarrow \beta_1 m_{t-1} + (1 - \beta_1) g_t \quad &\text{(momentum)} \\ v_t &\leftarrow \beta_2 v_{t-1} + (1 - \beta_2) g_t^2 \quad &\text{(variance)} \\ \hat{m}_t &\leftarrow m_t / (1 - \beta_1^t), \quad \hat{v}_t \leftarrow v_t / (1 - \beta_2^t) \quad &\text{(bias correction)} \\ V &\leftarrow V + \alpha \frac{\hat{m}_t}{\sqrt{\hat{v}_t} + \epsilon} \quad &\text{(parameter update)} \end{aligned} \tag{2.19}\]

where \(g_t\) is the gradient at step \(t\), \(\beta_1 = 0.9\) and \(\beta_2 = 0.999\) are typical, and \(\epsilon = 10^{-8}\) prevents division by zero.

Adam typically converges faster than vanilla gradient descent and is less sensitive to learning rate tuning. The adaptive per-parameter learning rates help in problems with varying gradient magnitudes across parameters.

2.8.3 Learning Rate Schedules

Instead of a fixed learning rate, schedules decay \(\eta\) over time to enable large initial steps (fast progress) followed by small refinements (precision):

• Step decay: \(\eta_t = \eta_0 \cdot \gamma^{\lfloor t / k \rfloor}\) (reduce by factor \(\gamma\) every \(k\) epochs)
• Exponential decay: \(\eta_t = \eta_0 e^{-\lambda t}\)
• Cosine annealing: \(\eta_t = \eta_{\min} + \frac{1}{2}(\eta_0 - \eta_{\min})(1 + \cos(\pi t / T))\)

Learning rate schedules are especially useful for training to convergence without extensive hyperparameter tuning.

Key Takeaway: Choosing an Optimizer

When to use each optimizer:

• Vanilla GD: Simple problems, well-tuned learning rate available, or for pedagogical clarity
• Adam: Default choice for most problems; robust to learning rate, fast convergence, handles sparse gradients well
• SGD with momentum: When you need the theoretical guarantees of SGD (e.g., convergence proofs) but want faster practical convergence

Hyperparameter guidelines: - Adam: \(\alpha = 0.001\) to \(0.1\), default \(\beta_1 = 0.9\), \(\beta_2 = 0.999\) - GD: \(\eta = 0.01\) to \(0.1\), may need careful tuning - Learning rate schedules: Helpful when training for many epochs

2.9 Real-World Application: LLM Preference Learning

We now apply all three parameter learning methods to a realistic preference learning scenario inspired by language model alignment. While production LLM alignment uses datasets like Stanford Human Preferences (SHP) or Anthropic’s HH-RLHF, we construct a synthetic dataset that captures key properties of real preference data: noisy labels, varying item quality, and response embeddings.

2.9.1 Dataset: Simulated LLM Response Preferences

We simulate a setting where a language model generates multiple responses to prompts, and human annotators provide pairwise preferences. Each response is represented by a learned embedding (e.g., from a pretrained model), and the true utility is a linear function of this embedding plus noise.

This synthetic dataset mimics real LLM preference data: responses have embedding representations, utilities are learned functions of embeddings, and annotations contain noise.

Label Noise: Random vs. Systematic

The 10% uniform label noise above is a simplification. In real annotation pipelines, noise is often systematic rather than random: annotators may have consistent biases (preferring verbose responses), may be influenced by presentation order, or may satisfice rather than carefully evaluate. Uniform noise attenuates the learned utilities toward zero (biasing toward equal preference) but preserves their ranking. Systematic noise, by contrast, can reverse rankings—if annotators consistently prefer item \(j\) for reasons unrelated to the true objective (e.g., surface fluency over factual accuracy), the MLE will learn the annotators’ biases as if they were genuine preferences. This connects to the inversion problem discussed in Chapter 6: observed choices may not reflect underlying preferences. Robust estimation methods that model annotator-specific biases or down-weight unreliable annotations can mitigate this issue.

2.9.2 Applying All Three Learning Methods

We apply MLE, Bayesian inference, and online learning (Elo) to the same data and compare results.

2.9.3 Key Observations

The three methods yield similar performance on this synthetic LLM preference task:

1. MLE is fastest and most scalable, suitable for large-scale applications
2. Bayesian inference via MCMC provides posterior distributions over utilities, enabling uncertainty quantification—the marginal plot shows how posterior samples vary, and error bars show 95% credible intervals
3. Online (Elo) learns incrementally, ideal for streaming data but may be less data-efficient than batch methods

All methods successfully recover utilities correlated with the ground truth despite 10% label noise, demonstrating robustness. In production LLM alignment:

• Data scale: Real datasets have 10K-100K+ comparisons
• Cold start: New responses have no comparison history; requires initialization strategies
• Computational cost: MCMC becomes expensive; MLE or online methods preferred
• Temporal drift: User preferences may evolve; online methods naturally adapt

Connecting to DPO

Recall from Section 1.2 that Direct Preference Optimization (DPO) for language models is equivalent to Bradley-Terry MLE where the “utility” is \(\beta \log \frac{\pi_\theta(y \mid x)}{\pi_{\text{ref}}(y \mid x)}\). The MLE techniques developed in this chapter directly apply to DPO training: regularization prevents overfitting to preference data, and optimization methods (Adam, learning rate schedules) accelerate convergence.

Common Pitfall: DPO’s Hidden Assumptions

DPO is often described as “reward-model-free,” but it is not assumption-free. DPO’s implicit reward is \(r^*(y \mid x) = \beta \log \frac{\pi_\theta(y \mid x)}{\pi_{\text{ref}}(y \mid x)}\), which means: (1) the recovered reward depends on the reference policy \(\pi_{\text{ref}}\) — different reference models yield different implicit rewards; (2) preferences are assumed to follow Bradley-Terry (i.i.d. Gumbel noise), so IIA violations in human judgments propagate silently; (3) the hyperparameter \(\beta\) controls the tradeoff between staying close to \(\pi_{\text{ref}}\) and optimizing for preferences — too small and the model barely moves; too large and it overfits to noisy labels. Always validate DPO-trained models against held-out preference data.

2.10 Summary

• This chapter develops three complementary approaches to estimating preference model parameters from observed comparison data, each with distinct tradeoffs in scalability, uncertainty quantification, and data requirements.
• Maximum Likelihood Estimation (MLE) finds point estimates by maximizing \(\ell(V) = \sum \log \sigma(V_j - V_k)\) via gradient ascent. It is fast, scalable, and the foundation for DPO training in language model alignment.
• Bayesian inference via Markov Chain Monte Carlo (MCMC) provides full posterior distributions over parameters, enabling uncertainty quantification—but at substantially higher computational cost. The Laplace approximation offers a cheaper Gaussian approximation to the posterior, essential for GP-based preference models where the non-Gaussian likelihood makes exact inference intractable.
• Online learning (Elo ratings) processes comparisons one at a time as streaming data. Elo is precisely stochastic gradient ascent on the Bradley-Terry log-likelihood with step size \(K\), bridging a 70-year-old rating system to modern optimization.
• Regularization (L2 penalty, early stopping) prevents overfitting, especially when comparisons are sparse. L2 regularization is equivalent to MAP estimation with a Gaussian prior, connecting frequentist and Bayesian perspectives.
• Cross-validation provides principled model selection—choosing regularization strength, model dimensionality, or kernel hyperparameters—by estimating out-of-sample performance without a separate test set.
• Evaluation requires multiple metrics: AUC measures ranking accuracy, log-likelihood measures calibration quality, and calibration error directly assesses whether predicted probabilities match observed frequencies.
• In practice, all three methods often recover similar utility estimates on well-specified problems; the choice depends on whether you need uncertainty (Bayesian), scalability (MLE), or streaming updates (online).

2.11 Quick Check

Test your understanding before proceeding to the exercises.

1. Why does the Bradley-Terry log-likelihood have a unique maximum when the comparison graph is strongly connected, but may not otherwise?

2. An Elo system uses \(K = 32\). After a game where the favorite (predicted 80% win probability) loses, how many rating points does each player gain/lose? What if \(K = 16\)?

3. You fit a Bradley-Terry model with no regularization on a sparse dataset (50 items, 100 comparisons). Some items have never been compared. What happens to the MLE for those items? How does L2 regularization help?

4. A colleague says “our model has 95% AUC on the test set, so it’s excellent.” What additional evaluation would you recommend, and why might high AUC still mask poor performance?

2.12 Discussion Questions

• In the synthetic experiments, why is the Bayes optimal AUC less than 1.0 even though we know the true parameters? What does this reveal about the fundamental limits of prediction from noisy preference data?

• How does L2 regularization affect the bias-variance tradeoff in Bradley-Terry estimation? Under what data conditions (sample size, noise level, number of items) would you expect regularization to have the largest impact on test performance?

• When would you prefer online learning (Elo) over batch learning (MLE) for preference model estimation? Consider computational cost, data arrival patterns, and statistical efficiency. Can you design a hybrid approach that combines benefits of both?

• The Bayesian approach via MCMC provides posterior distributions over parameters, while MLE gives point estimates. Beyond uncertainty quantification, what practical advantages might the full posterior provide? How would you use posterior samples to make decisions (e.g., which items to present to users)?

• Cross-validation assumes that folds are exchangeable—that the data distribution is the same across all folds. For sequential preference data (e.g., chess games ordered in time, or LLM preferences from a changing user population), this assumption may be violated. How should cross-validation be adapted for temporal data? What are the risks of using standard k-fold CV on sequential data?

• In the LLM preference learning example, all three methods (MLE, Bayesian, Elo) achieved similar test AUC despite different training procedures. Under what circumstances would you expect the methods to diverge in performance? Consider data scale, noise level, model mis-specification, and computational budget.

2.13 Bibliographic Notes

Maximum likelihood estimation for preference models dates back to Bradley and Terry (1952)’s original work on paired comparisons. The connection to modern machine learning was established through applications in ranking (Herbrich, Minka, and Graepel 2006) and recommender systems (Koren, Bell, and Volinsky 2009). Hunter (2004) provided efficient MM algorithms for Bradley-Terry MLE that scale to large problems.

Bayesian inference for preference data has a long history in psychometrics and experimental design. Davidson (1970) developed Bayesian approaches for paired comparisons. Modern MCMC methods for Bradley-Terry models are surveyed in Caron and Doucet (2012). The connection between L2 regularization and Gaussian priors (MAP estimation) is standard in Bayesian machine learning (Murphy 2012).

The Elo rating system was introduced by Elo (1978) for chess rankings and has since been applied broadly to competitive games (Glickman 1999 introduced the Glicko system with uncertainty estimates), online platforms (Herbrich, Minka, and Graepel 2006 for Xbox matchmaking), and information retrieval. The interpretation of Elo as stochastic gradient descent on the Bradley-Terry log-likelihood clarifies its connection to machine learning (Weng and Lin 2011).

Regularization in statistical learning has roots in ridge regression (Hoerl and Kennard 1970) and has become central to modern machine learning (Hastie, Tibshirani, and Friedman 2009). Early stopping as implicit regularization was analyzed by Yao, Rosasco, and Caponnetto (2007). The bias-variance tradeoff provides the theoretical foundation for why regularization improves generalization (Geman, Bienenstock, and Doursat 1992).

Cross-validation was formalized by Stone (1974) and Geisser (1975) for model selection. Kohavi (1995) provided practical guidance for k-fold CV. Nested cross-validation to avoid selection bias was emphasized by Cawley and Talbot (2010). Temporal validation strategies for time-series data are discussed in Bergmeir, Hyndman, and Koo (2018).

Optimization methods for machine learning are surveyed in Ruder (2016). Adam was introduced by Kingma and Ba (2014) and has become the default optimizer for deep learning. Convergence analysis for gradient descent on convex problems (including logistic regression, which includes Bradley-Terry) is classical (Boyd and Vandenberghe 2004). Learning rate schedules and their impact on generalization are discussed in Loshchilov and Hutter (2016).

LLM alignment via preference learning gained prominence with Christiano et al. (2017)’s introduction of RLHF. The connection to Bradley-Terry and reward modeling was made explicit in Ouyang et al. (2022) (InstructGPT). Direct Preference Optimization (DPO) (Rafailov et al. 2023) showed that RLHF can be reformulated as Bradley-Terry MLE, eliminating the need for a separate reward model. Recent work explores calibration (Stiennon et al. 2020), robustness to noise (al. 2022), and scaling laws (Gao, Schulman, and Hilton 2022) for preference-based LLM training.

For further reading: Agresti (2002) provides comprehensive coverage of categorical data analysis including paired comparisons. Marden (1995) covers ranking models from a statistical perspective. Liu (2011) surveys learning-to-rank methods in information retrieval, many of which build on preference models.

Essential Reading

If you read only five papers from this chapter’s references, make them these:

1. Elo (1978) — The Elo rating system: the most widely deployed preference learning algorithm in history
2. Herbrich, Minka, and Graepel (2006) — TrueSkill: Bayesian preference learning with uncertainty, the Elo successor
3. Rafailov et al. (2023) — DPO as Bradley-Terry MLE, unifying reward modeling and policy optimization
4. Ouyang et al. (2022) — InstructGPT: scaling RLHF to large language models
5. Hastie, Tibshirani, and Friedman (2009) — The statistical learning textbook covering regularization, cross-validation, and model selection foundations

2.14 Further Reading

For readers who want to go deeper into the topics introduced in this chapter, we recommend the following:

• Hunter (2004), “MM Algorithms for Generalized Bradley-Terry Models” — Efficient algorithms for MLE that scale to large comparison datasets, including extensions to ties and home-field advantage.
• Caron and Doucet (2012), “Efficient Bayesian Inference for Generalized Bradley-Terry Models” — Modern MCMC and variational methods for Bayesian preference learning, including techniques for handling large-scale data.
• Glickman (1999), “Parameter Estimation in Large Dynamic Paired Comparison Experiments” — The Glicko rating system, which extends Elo with per-player uncertainty estimates that decay with inactivity, addressing several limitations of fixed K-factor Elo.
• Rasmussen and Williams (2006), Gaussian Processes for Machine Learning, Ch. 3 — Comprehensive treatment of the Laplace approximation and expectation propagation for GP classification, the theoretical foundation for the GP inference methods used in this chapter.
• Gneiting and Raftery (2007), “Strictly Proper Scoring Rules, Prediction, and Estimation” — The definitive treatment of proper scoring rules and calibration, explaining why cross-entropy (log loss) is the natural loss for preference learning and how to assess whether learned probabilities are well-calibrated.
• Ouyang et al. (2022), “Training Language Models to Follow Instructions with Human Feedback” — The InstructGPT paper that demonstrated RLHF at scale, showing how the MLE, Bayesian, and online methods in this chapter are applied to real LLM alignment.
• Hastie, Tibshirani, and Friedman (2009), The Elements of Statistical Learning — The standard reference for regularization theory, bias-variance tradeoff, and cross-validation, providing the statistical foundations for the model selection techniques discussed here.

2.15 Exercises

Exercises are marked with difficulty levels: () for introductory, () for intermediate, and () for challenging.

2.15.1 Gradient Derivation for Plackett-Luce (*)

The Plackett-Luce model extends Bradley-Terry to full rankings. Given a ranking \((j_1 \succ j_2 \succ \cdots \succ j_M)\), the likelihood is: \[ p(\text{ranking} \mid V) = \prod_{k=1}^{M-1} \frac{\exp(V_{j_k})}{\sum_{\ell=k}^M \exp(V_{j_\ell})} \tag{2.20}\]

1. Write the log-likelihood for a single ranking as a function of utilities \(V\).

2. Derive the gradient \(\frac{\partial \log p}{\partial V_m}\) for an arbitrary item \(m\). Hint: Consider three cases: \(m\) appears at position \(k\), \(m\) appears after position \(k\), and \(m\) does not appear in the ranking.

3. Implement gradient ascent for Plackett-Luce on simulated ranking data. Compare convergence to Bradley-Terry MLE—which converges faster and why?

2.15.2 L2 Regularized Bradley-Terry (**)

1. Implement Bradley-Terry MLE with L2 regularization for a range of \(\lambda\) values. Generate synthetic data with \(M = 20\) items and vary the number of comparisons from 50 to 500. Plot test AUC vs \(\lambda\) for each dataset size.

2. Explain why the optimal \(\lambda\) decreases as the number of comparisons increases. At what rate does it decay?

3. Derive the Hessian matrix of the regularized log-likelihood. Under what conditions is it positive definite (ensuring a unique global maximum)?

2.15.3 K-Fold Cross-Validation Implementation (**)

1. Implement 5-fold cross-validation for Bradley-Terry estimation from scratch (without using sklearn or similar libraries). Your implementation should:

• Randomly partition comparison data into 5 folds
• Train on 4 folds, validate on 1 fold
• Repeat for all 5 folds
• Return mean and standard deviation of validation AUC

2. Compare your CV implementation to a single 80/20 train/test split over 20 random seeds. Which provides a more stable performance estimate?

3. Extend your implementation to stratified CV: ensure each fold has approximately equal proportions of wins for each item. Why might stratification improve CV estimates for imbalanced data?

2.15.4 Learning Rate Sensitivity Analysis (*)

1. For Bradley-Terry MLE on synthetic data (\(M = 15\) items, 100 comparisons), experiment with learning rates \(\eta \in \{0.001, 0.01, 0.05, 0.1, 0.5, 1.0\}\). Plot the training loss curve for each learning rate.

2. Identify the learning rate that achieves the lowest final loss. What happens with learning rates that are too large? Too small?

3. Implement a learning rate schedule (e.g., exponential decay \(\eta_t = \eta_0 \cdot 0.95^t\)) and compare to fixed learning rate. Does the schedule improve final performance?

2.15.5 MCMC Diagnostics (**)

The Metropolis-Hastings implementation in Section 2.4 produces a chain of samples. Assess convergence quality:

1. Implement the effective sample size (ESS) diagnostic: ESS estimates how many independent samples the chain is equivalent to, accounting for autocorrelation. For a chain \(\{V^{(t)}\}_{t=1}^T\), the ESS for parameter \(V_j\) is approximately: \[ \text{ESS}_j = \frac{T}{1 + 2\sum_{k=1}^K \rho_k} \tag{2.21}\] where \(\rho_k\) is the autocorrelation at lag \(k\).

2. Run the MH algorithm from Section 2.4 with different proposal step sizes \(\tau \in \{0.01, 0.05, 0.1, 0.5\}\). Plot ESS vs \(\tau\). What happens when \(\tau\) is too small? Too large?

3. Implement trace plots for multiple chains (run MH 3 times with different initializations). Do all chains converge to the same stationary distribution?

2.15.6 Optimization Method Comparison (**)

1. Implement gradient descent with momentum: \(m_t \leftarrow \beta m_{t-1} + \nabla \mathcal{L}(V_t)\), \(V_{t+1} \leftarrow V_t + \eta m_t\) where \(\beta \in [0, 1)\) controls momentum.

2. On the same synthetic Bradley-Terry problem, compare four optimizers: vanilla GD, GD with momentum (\(\beta = 0.9\)), Adam, and RMSprop. Plot convergence curves (loss vs iteration).

3. For each optimizer, find the best learning rate via grid search. Which optimizer is most sensitive to learning rate tuning?

2.15.7 Convergence Proof (***)

Prove that gradient ascent on the Bradley-Terry log-likelihood converges to the global maximum (assuming the maximum exists).

1. Show that the Bradley-Terry log-likelihood is strictly concave when the comparison graph is strongly connected (every pair of items is connected by a directed path of comparisons).

2. Prove that gradient ascent with sufficiently small step size \(\eta\) converges to the unique global maximum. Hint: Use the fact that the gradient vanishes only at the maximum for strictly concave functions.

3. What happens when the comparison graph is not strongly connected? Construct an example with multiple disconnected components and characterize the set of maximum likelihood estimators.

2.15.8 Calibration Metrics (*)

1. Implement a calibration plot: bin predicted probabilities into 10 intervals \([0, 0.1), [0.1, 0.2), \ldots, [0.9, 1.0]\), and for each bin, compute the average predicted probability and the empirical frequency of wins.

2. Generate synthetic Bradley-Terry data and fit two models: one correctly specified (Bradley-Terry) and one mis-specified (assume all items have equal utility). Plot calibration curves for both. Which is better calibrated?

3. Define the Expected Calibration Error (ECE): \(\text{ECE} = \sum_{b=1}^B \frac{|B_b|}{N} |\bar{p}_b - \bar{y}_b|\) where \(\bar{p}_b\) is the average predicted probability in bin \(b\), \(\bar{y}_b\) is the empirical frequency, and \(|B_b|\) is the number of predictions in bin \(b\). Compute ECE for your models.

2.15.9 Online to Batch Convergence (*)

1. Implement Elo with a decreasing K-factor: \(K_t = K_0 / \sqrt{t}\) where \(t\) is the iteration number. This is known as the Robbins-Monro condition for stochastic approximation.

2. On synthetic Bradley-Terry data, run Elo with decreasing \(K_t\) and compare the final learned parameters to batch MLE. How close do they converge?

3. Prove (or argue informally) that Elo with \(K_t = \eta / \sqrt{t}\) converges to the MLE in the limit as \(t \to \infty\). Under what conditions does this hold?

2.15.10 Hyperparameter Tuning with Nested Cross-Validation (***)

To obtain an unbiased estimate of generalization performance when hyperparameters are selected via CV, we use nested (double) CV:

• Outer loop: K-fold CV to estimate generalization
• Inner loop: For each outer fold, use K-fold CV on the training data to select hyperparameters

1. Implement nested 5-fold CV for Bradley-Terry with L2 regularization. The inner loop tunes \(\lambda\), the outer loop estimates test AUC.

2. Compare the nested CV test AUC estimate to: (i) a single train/test split with CV on training data for \(\lambda\) selection, and (ii) CV test AUC when \(\lambda\) is selected using the outer CV test set (data leakage). Which is more optimistic? Pessimistic?

3. Why is nested CV important? Give an example where selecting hyperparameters on the same data used for final evaluation leads to overly optimistic performance estimates.

2.15.11 Real-World Dataset Application (***)

Apply the methods from this chapter to a real preference dataset:

1. Obtain a dataset such as the Jester jokes dataset (user ratings), a subset of MovieLens, or chess game outcomes from Lichess. Describe the data: number of items, number of comparisons, sparsity.

2. Apply all three methods (MLE with regularization, Bayesian inference, online Elo) and compare their performance using multiple metrics (AUC, log-likelihood, calibration error). Use cross-validation to tune hyperparameters.

3. Visualize the learned item parameters. Do they agree with intuition (e.g., highly-rated movies have high utility)? Identify the top-5 and bottom-5 items according to each method—do the methods agree?

4. Discuss practical challenges encountered: computational cost, cold-start items, missing data, temporal effects. How would you address these in a production system?

2.15.12 Bias-Variance Tradeoff Demonstration (**)

1. Generate synthetic Bradley-Terry data with \(M = 10\) items and vary the training set size \(n \in \{20, 50, 100, 200, 500\}\) comparisons. For each \(n\) and several regularization strengths \(\lambda\), fit models and compute:

• Bias: Average difference between learned and true parameters
• Variance: Standard deviation of learned parameters across 50 random datasets

2. Plot bias and variance vs \(\lambda\) for each training set size. Verify that as \(\lambda\) increases, bias increases and variance decreases.

3. Plot test AUC vs \(\lambda\) and identify the optimal \(\lambda\) for each \(n\). How does the optimal regularization strength change with dataset size?

Intended Learning Outcomes

By the end of this chapter you will be able to:

• Define the measurement problem for user preference elicitation and distinguish it from the learning problem in Chapter 3.
• Derive the Fisher information for Rasch/Bradley-Terry models and explain why items with \(p \approx 0.5\) are most informative.
• Compare A-optimal, D-optimal, and E-optimal design criteria for selecting informative queries.
• Apply Laplace approximation to update posterior beliefs about user preferences in real-time.
• Implement active selection policies that outperform random sampling in sample efficiency.
• Extend Fisher information analysis to non-linear scoring functions via local linearization.
• Apply information-theoretic acquisition functions to actively select queries for Gaussian Process preference models, building on the GP foundations from Chapters 2-3.
• Explain how D-optimal design applies to Direct Preference Optimization (DPO) for LLM alignment and derive the ADPO algorithm.
• Analyze active preference learning in robotics, including trajectory comparison and reward function inference.

2.16 Chapter Overview

Chapter 1 developed models for how preferences arise from latent utilities. Chapter 2 showed how to estimate these utilities from observed comparisons. This chapter addresses the complementary question: given that human feedback is expensive, how should we choose which comparisons to request?

This is the measurement problem in preference elicitation. Unlike the learning problem (which assumes data is given), the measurement problem actively designs experiments to maximize information gained per query. Consider training an LLM via RLHF: collecting 100,000 human preference labels is expensive and time-consuming. If we could achieve the same alignment quality with 20,000 strategically selected comparisons, we would save 80% of annotation cost.

The central insight is that not all comparisons are equally informative. Asking whether humans prefer “Hello!” to “Hi there!” reveals little about model quality. Comparing two substantively different responses to a complex prompt provides more signal. The mathematical framework of Fisher information and optimal experimental design formalizes this intuition.

Chapter Structure. We build from simple to complex settings:

1. Scalar preferences (Section 2.17): The Rasch model and Fisher information
2. Multi-dimensional preferences (Section 2.17.1): Factor models and optimal design criteria (A/D/E-optimal)
3. Preference functions (Section 2.18): Linear and non-linear scoring functions
4. Nonparametric models (Section 2.19): GP-based active learning with information-theoretic acquisition
5. LLM alignment (Section 2.20): Active DPO for large language models
6. Applications: Metric elicitation (Section 2.17.3) and robotics (Section 2.18.1)

Connections to Prior Chapters:

Concept	Chapter 1-2	This Chapter
Bradley-Terry model	Likelihood, MLE (Section 1.6.2)	Fisher information, query selection
Factor models \(U^\top V\)	Parameter estimation (Section 1.6)	D-optimal pair selection
GP preference models	Laplace inference (Section 2.4.2)	Information-gain acquisition
DPO loss	Objective function (Section 1.2)	ADPO active selection

Historical Notes. Active learning for preferences has roots in multiple fields:

• Psychometrics (1960s): Computer-adaptive testing used Fisher information to select test items matching student ability
• Optimal experimental design (1970s): Fedorov and Kiefer developed A/D/E-optimality for linear models
• Bayesian experimental design (1990s): Chaloner & Verdinelli unified information-theoretic approaches
• RLHF/Active DPO (2020s): Applying these ideas to LLM alignment at scale

“The purpose of optimal design is to achieve the desired precision with minimum cost.” — V.V. Fedorov (1972)

2.17 Measurement of User Preference Vector

When items’ appeals \(V_j\) are known or pre-calibrated, we can learn a new user’s appetite \(U\) quickly by choosing informative items online. Asking only easy or only hard items gives near-deterministic responses that teach little. The key tool for quantifying “informativeness” is Fisher information.

Definition: Fisher Information

Definition 2.1 For a parametric model \(p(Y \mid \theta)\), the Fisher Information about parameter \(\theta\) is: \[ \mathcal{I}(\theta) = \mathbb{E}\left[-\frac{\partial^2}{\partial \theta^2} \log p(Y \mid \theta)\right] = \mathbb{E}\left[\left(\frac{\partial}{\partial \theta} \log p(Y \mid \theta)\right)^2\right] \] Fisher Information quantifies how much a single observation reveals about \(\theta\). Higher Fisher Information means more precise estimation from each observation. The Cramér-Rao bound states that the variance of any unbiased estimator is at least \(\mathcal{I}(\theta)^{-1}\).

The Rasch model makes this precise. Recall from Section 1.6 that for a candidate item \(j\), the Bernoulli success probability is \(p_j(U) = \sigma(U + V_j).\) The Fisher information about \(U\) from a single response is \[\mathcal I_j(U) = \mathbb{E} \left[-\frac{\partial^2}{\partial U^2}\log p(Y \mid U, V_j)\right] = p_j(U) (1 - p_j(U)). \tag{2.22}\]

Proposition: Optimal Item Difficulty

Proposition 2.1 For the Rasch model with \(p_j(U) = \sigma(U + V_j)\), the Fisher Information \(\mathcal{I}_j(U) = p_j(1-p_j)\) is maximized when \(p_j(U) = 0.5\), which occurs when item difficulty \(-V_j\) equals user ability \(U\).

Proof

The function \(f(p) = p(1-p)\) is a downward parabola with roots at \(p=0\) and \(p=1\). Taking the derivative: \(f'(p) = 1 - 2p = 0 \Rightarrow p = 0.5\). At this point, \(f(0.5) = 0.25\), which is the maximum. Since \(p_j(U) = \sigma(U + V_j) = 0.5\) when \(U + V_j = 0\), the optimal item has \(V_j = -U\).

Worked Example: Fisher Information for Item Selection

A user has estimated ability \(\hat{U} = 1.0\). We have three candidate items with appeals \(V_1 = -2.0\) (hard), \(V_2 = -1.0\) (matched), and \(V_3 = 1.0\) (easy). Which item should we ask next?

Step 1. Compute predicted success probabilities: \[p_1 = \sigma(1.0 + (-2.0)) = \sigma(-1.0) \approx 0.269\] \[p_2 = \sigma(1.0 + (-1.0)) = \sigma(0.0) = 0.500\] \[p_3 = \sigma(1.0 + 1.0) = \sigma(2.0) \approx 0.881\]

Step 2. Compute Fisher information for each item: \[\mathcal{I}_1 = p_1(1-p_1) = 0.269 \times 0.731 \approx 0.197\] \[\mathcal{I}_2 = p_2(1-p_2) = 0.500 \times 0.500 = 0.250\] \[\mathcal{I}_3 = p_3(1-p_3) = 0.881 \times 0.119 \approx 0.105\]

Step 3. Select the most informative item: \(j^* = \arg\max_j \mathcal{I}_j = 2\) (the matched item).

Interpretation: Item 2, whose difficulty \(-V_2 = 1.0\) matches the user’s ability \(\hat{U} = 1.0\), is most informative because it produces responses closest to 50-50. The easy item (\(V_3\)) is least informative — the user almost certainly succeeds, so the response tells us little about their ability. This is the principle behind computerized adaptive testing: the test “follows” the student, always selecting questions near their ability level.

This result has a natural interpretation: items that are too easy (\(p \approx 1\)) or too hard (\(p \approx 0\)) yield near-deterministic responses that teach little about the user. Items matched to the user’s ability (\(p \approx 0.5\)) are maximally informative. So the best next item is one whose difficulty (\(-V_j\)) is close to the current estimate of \(U\). Active elicitation policies therefore “hover” around the user’s current location, rapidly shrinking uncertainty. Place a Gaussian prior \(U \sim \mathcal N(0,\sigma_0^2)\). After observing independent items \(\mathcal J\), a Laplace (or IRLS) update for \(U\) uses the score and observed information \[S(U) = \sum_{j\in\mathcal J} (y_j - p_j(U)), \qquad \mathcal I(U) = \sum_{j\in\mathcal J}p_j(U) (1 - p_j(U)) + \tau_0, \quad \tau_0 = \sigma_0^{-2}. \tag{2.23}\] A Newton step is \(\hat U \leftarrow \hat U + S(\hat U)\mathcal I(\hat U)^{-1}.\) The approximate posterior variance is \(\widehat{\mathrm{Var}}(U) \approx \mathcal I(\hat U)^{-1}.\) An item-selection rule that maximizes expected information picks \(j_t = \arg\max_j \; p_j(\hat U_{t-1}) (1 - p_j(\hat U_{t-1})).\) For evaluation, we can use reliability. With population variance \(\mathrm{Var}(U^\star)=\sigma_U^2\), reliability is the fraction of total variance explained by the test rather than estimation noise: \[ \text{Rel} \approx 1 - \frac{1}{N}\sum_{i=1}^N \frac{\widehat{\mathrm{Var}}(U_i)}{\sigma_U^2}. \tag{2.24}\] Below, the code simulates many users, a bank of calibrated items, and compares an Fisher policy to a random policy. We track reliability after each query count \(t\).

First, we set up the simulation with \(N\) users, \(M\) calibrated items, and define helper functions for Bayesian updating:

Next, we define the Bayesian update rule and the two item selection policies—Fisher-active (maximizing information) and random:

Now we run the simulation, comparing both policies across all users:

Finally, we visualize the results comparing Fisher-active vs random item selection:

Key Takeaway: Active Beats Random

Fisher-active item selection achieves higher reliability with fewer queries than random selection. The gain comes from targeting items near \(p=0.5\), where each response is maximally informative. This principle—measure where uncertainty is highest—underlies all active learning methods in this chapter.

Assumption: Known Item Parameters

The Fisher information framework above assumes item parameters (\(V_j\), \(Z_j\)) are known or pre-calibrated before elicitation begins. In practice, item parameters must often be estimated jointly with user preferences—this is the cold-start problem in recommender systems. When item parameters are uncertain, errors in item calibration propagate into suboptimal query selection: the system may ask about items it thinks are informative but are not. Joint estimation of user and item parameters requires different approaches, such as alternating optimization or fully Bayesian models that maintain uncertainty over both.

2.17.1 Factor Models: Multi-Dimensional Preferences

In practice, a single “ability” parameter may not capture the diversity of user preferences. Factor models generalize Rasch by giving each user a \(K\)-dimensional embedding \(U_i \in \mathbb R^K\) and each item a \(K\)-dimensional embedding \(V_j \in \mathbb R^K\), plus optional bias \(Z_j\). The linear predictor is \(H_{ij} = U_i^\top V_j + Z_j\) where \(p(Y_{ij}=1 \mid U_i, V_j, Z_j) = \sigma(H_{ij}).\)

A concrete instance is performance metric elicitation (Hiranandani et al. 2019). In binary classification, practitioners often have implicit preferences over classifiers that don’t match standard metrics like accuracy or F1—for instance, in medical diagnosis, the cost of a false negative (missed disease) may differ greatly from a false positive (unnecessary treatment). This is a \(K=2\) factor model where “items” are classifiers with known confusion matrices \(V_\theta = (\text{TP}_\theta, \text{TN}_\theta)\), and the “user preference” is the unknown metric weights \(\mathbf{m} = (m_{11}, m_{00})\). The utility \(\mathbf{m}^\top V_\theta = m_{11} \cdot \text{TP}_\theta + m_{00} \cdot \text{TN}_\theta\) is exactly the factor model form with known item parameters.

For a given user \(U\) and an item \(j\) with known parameters, the Bernoulli log-likelihood is \[\ell(U; y, j) = y \log \sigma(H) + (1-y)\log (1-\sigma(H)) \tag{2.25}\] The gradient with respect to \(U\) is \(\nabla_U \ell = (y - \sigma(H)) V_j.\) The expected Fisher Information per item is the negative expected Hessian: \[ \mathcal I_j(U) = \mathbb E[\nabla_U \ell \nabla_U \ell^\top ] = \sigma(H)(1-\sigma(H)) V_j V_j^\top. \tag{2.26}\] So each queried item contributes a rank-1 matrix in the direction of \(V_j\), scaled by the variance term \(\sigma(H)(1-\sigma(H))\). For a sequence of items \({j_t}\), the cumulative information is \[\mathcal I(U) = \sum_t \sigma(H_{j_t})(1-\sigma(H_{j_t})) V_{j_t} V_{j_t}^\top. \tag{2.27}\]

Assumption: Correct Model Specification

Fisher information quantifies the informativeness of a query under the assumed model. If the model is misspecified—for example, if preferences are not logistic, or if the factor structure has the wrong dimensionality \(K\)—then queries optimized for the Fisher criterion may not be optimal for learning the true preference structure. Under misspecification, information-theoretic criteria such as mutual information or Bayesian approaches that integrate over model uncertainty can be more robust. In practice, it is worth checking sensitivity to the assumed model by comparing active learning performance across different model specifications.

In multiple dimensions, information is a matrix. Classical optimal design offers various criteria for selecting informative queries:

Definition: Optimal Design Criteria

Definition 2.2 Given a Fisher Information matrix \(\mathcal{I}(U)\), the classical optimal experimental design criteria are:

• A-Optimal (Average): Minimize \(\text{tr}(\mathcal{I}^{-1})\)—the average variance of parameter estimates
• D-Optimal (Determinant): Maximize \(\det(\mathcal{I})\)—the volume shrinkage of the posterior ellipsoid
• E-Optimal (Eigenvalue): Maximize \(\lambda_{\min}(\mathcal{I})\)—the precision in the worst-case direction

All three reduce uncertainty, but emphasize different aspects: A-optimal targets average precision, D-optimal targets overall information volume, and E-optimal targets the least-informed direction.

Common Pitfall: Confusing A-Optimal, D-Optimal, and E-Optimal

These three criteria optimize different objectives and can select different queries. A-optimal minimizes average variance (good when all parameters matter equally), D-optimal maximizes the determinant of the information matrix (shrinks the posterior ellipsoid volume — good for overall uncertainty), and E-optimal maximizes the minimum eigenvalue (guards against worst-case directions). A common mistake is to treat them as interchangeable. In practice: D-optimal naturally encourages diversity in selected items (redundant items give diminishing information), while E-optimal is conservative (focuses all effort on the least-informed direction). Choose the criterion based on your downstream task — if you need accurate ranking of all items, A-optimal is natural; if you need a single best decision, E-optimal may be preferable.

Adaptive measurement picks the next item \(j\) to maximize an acquisition function such as \(\det(\mathcal I+\mathcal I_j)\). We also use reliability as the evaluation metric here. If \(\Sigma_U\) is the population covariance and \(\widehat{\Sigma}_{\text{err}}\) the average posterior covariance, then \(\text{Reliability} = 1 - \mathrm{tr}(\widehat{\Sigma}_{\text{err}}) \mathrm{tr}(\Sigma_U)^{-1}.\) This generalizes the Rasch reliability to multi-dimensional latent traits. Below is a toy simulation with 2-dimensional users and items, comparing random item selection vs D-optimal Fisher active selection:

First, set up the factor model simulation with K-dimensional user and item embeddings:

Define the Bayesian update and D-optimal selection:

Run simulation comparing D-optimal vs random selection:

Visualize results:

2.17.2 Pairwise Preferences

We next discuss the measurement problem with pairwise data. Recall from Section 1.6.2 that the Bradley-Terry model specifies the probability that user \(i\) prefers item \(j\) over item \(k\) as \(p_{i}(j \succ k)=\sigma (U^\top(V_j-V_k) + Z_j-Z_k)\) with feature \(x_{jk}= V_j - V_k \in \mathbb R^K\) and offset \(b_{jk}=Z_j-Z_k\).

In metric elicitation, each oracle query asks: “Which classifier is better, \(h_\theta\) or \(h_{\theta'}\)?” The oracle’s answer is deterministic: \(\Omega(C_\theta, C_{\theta'}) = \mathbf{1}[\mathbf{m}^\top (V_\theta - V_{\theta'}) > 0]\), which is exactly a pairwise comparison with feature difference \(x = V_\theta - V_{\theta'}\). The deterministic oracle corresponds to the \(\sigma \to \text{step function}\) limit of Bradley-Terry.

For a single observation \(y \in \{0,1\}\) of \(j \succ k\) the per-pair log-likelihood is \[\ell(U; y, i, j, k)= y \log p + (1-y) \log (1-p_i). \tag{2.28}\]

Score and expected Fisher information for (U): \[\nabla_U \ell=(y-p),x_{jk}, \qquad \mathcal I_{jk}(U)=\mathbb E[-\nabla^2_U \ell] = w x_{jk} x_{jk}^\top, \tag{2.29}\] where \(w = p(1-p)\). For a sequence of queried pairs \({(j_t,k_t)}\) the cumulative information is \(\mathcal I(U)=\sum_t w_t,x_t x_t^\top.\) With a Gaussian prior \(U \sim \mathcal N(0, \Sigma_0)\) and a Laplace approximation, the posterior precision updates additively: \[ \Lambda_{t}=\Sigma_t^{-1}=\Sigma_{0}^{-1}+\sum_{s\le t} w_s,x_s x_s^\top. \tag{2.30}\] A single Newton step for the posterior mean after observing ((x,y)) is \[ \hat U \leftarrow \hat U + \Sigma_{t}^{\ }(y-p),x,\qquad p=\sigma(\hat U^\top x+b),\quad \Sigma_t = \left(\Lambda_{t-1}+w,xx^\top\right)^{-1}. \tag{2.31}\] This is the logistic-regression one-step IRLS update specialized to one new example. We evaluate candidates at the current \((\hat U,\Sigma)\). Write \(x\) for \(x_{jk}\) and \(w=\sigma(\hat U^\top x+b)\big(1-\sigma(\hat U^\top x+b)\big)\). Let \(\Lambda=\Sigma^{-1}\). Using the Sherman–Morrison formula, we obtain closed forms for all three design criteria:

Proposition: D-Optimal Acquisition via Sherman-Morrison

Proposition 2.2 For a current precision matrix \(\Lambda = \Sigma^{-1}\) and a candidate pair \((j,k)\) with feature difference \(x = V_j - V_k\) and variance weight \(w = p(1-p)\), the D-optimal acquisition function has closed form: \[ \Delta_D(j,k) = \log\det(\Lambda + w xx^\top) - \log\det(\Lambda) = \log(1 + w x^\top \Sigma x) \] This follows from the matrix determinant lemma: \(\det(A + uv^\top) = (1 + v^\top A^{-1} u)\det(A)\).

Pick the pair that maximizes \(\log(1 + w x^\top\Sigma x)\). This requires only a vector-matrix-vector product, making it efficient for online selection.

Myopic vs. Non-Myopic Query Selection

The D-optimal (and A/E-optimal) criteria above are greedy: they select each query to maximize the immediate information gain, without considering how the current query affects future query opportunities. The optimal policy would look ahead over a budget of \(T\) queries and select the sequence that maximizes total information. In practice, the greedy approach works well when queries are roughly exchangeable, but it can perform poorly in batch selection settings (selecting multiple queries simultaneously) because it ignores redundancy—two individually informative queries may provide overlapping information. Batch extensions typically add diversity mechanisms, such as penalizing queries whose feature vectors \(V_j - V_k\) are correlated with already-selected pairs.

• A-optimal (trace drop of covariance): \(\Delta_A(j,k);=;\mathrm{tr}(\Sigma)-\mathrm{tr}\big((\Lambda+w,xx^\top)^{-1}\big) = \frac{w,x^\top\Sigma^2 x}{1+w,x^\top\Sigma x}.\)

• E-optimal (raise the worst-direction information): Exact update of \(\lambda_{\min}(\mathcal I)\) needs an eigen update. A practical proxy is to maximize \(\Delta_E^{\text{proxy}}(j,k)= w,x^\top\Sigma x,\) which targets directions where current uncertainty \(x^\top\Sigma x\) is large.

End-to-end toy pipeline (rank 2, known items, active D-opt vs random). First, define helper functions for D-optimal gain and Bayesian updates:

Set up simulation parameters and precompute candidate pairs:

Define selection policies and run the simulation:

Visualize the results:

Key Takeaway: D-Optimal Design

For multi-dimensional preference vectors, D-optimal selection maximizes \(\log\det(\mathcal{I})\), shrinking the posterior ellipsoid in all directions. The Sherman-Morrison formula enables efficient computation: each candidate pair requires only a vector-matrix-vector product \(x^\top \Sigma x\). D-optimal design naturally encourages diversity—selecting pairs with redundant information directions provides diminishing log-det gain.

2.17.3 Metric Elicitation: Exploiting Quasiconcavity

The metric elicitation problem has special structure that enables even more efficient elicitation than general D-optimal design. A Linear Performance Metric (LPM) has the form: \[ \phi(C) = m_{11} \cdot \text{TP} + m_{00} \cdot \text{TN} + m_0 \tag{2.32}\] where the weights \((m_{11}, m_{00})\) encode tradeoffs between true positives and true negatives. Since only the ratio matters, we can parametrize as \(\mathbf{m} = (\cos\theta, \sin\theta)\) for \(\theta \in [0, 2\pi]\).

For medical diagnosis, \(m_{11} > m_{00}\) weights sensitivity (catching disease) over specificity (avoiding false alarms). For spam filtering, the reverse may hold. The key is that the practitioner’s implicit metric \(\mathbf{m}^*\) is unknown—we must learn it from pairwise comparisons.

Proposition: Quasiconcavity of LPM Composition

Proposition 2.3 For a quasiconcave LPM \(\phi\) that is monotonically increasing in TP and TN, and a parametrization \(\rho^+(\theta)\) of the upper boundary of the confusion matrix space \(\mathcal{C}\), the composition \(\phi \circ \rho^+\) is quasiconcave and unimodal on \([0, \pi/2]\).

Quasiconcavity means the function has a single peak—no local maxima to trap us. This enables binary search rather than gradient-based optimization:

Algorithm: LPM Elicitation via Binary Search

Input: Tolerance \(\epsilon > 0\), oracle \(\Omega\)

Initialize: \(\theta_a = 0\), \(\theta_b = \pi/2\)

While \(|\theta_b - \theta_a| > \epsilon\):

1. Divide \([\theta_a, \theta_b]\) into four equal intervals with boundaries \(A, B, C, D, E\)
2. Compute confusion matrices \(C_A, C_B, C_C, C_D, C_E\) for classifiers at each \(\theta\)
3. Query oracle: compare all adjacent pairs to find which interval contains the maximum
4. Update \([\theta_a, \theta_b]\) to the interval containing the maximum

Return: \(\hat{\mathbf{m}} = (\cos\hat\theta, \sin\hat\theta)\) where \(\hat\theta = (\theta_a + \theta_b)/2\)

Each iteration uses 4 queries and shrinks the search interval by factor of 2, giving \(O(\log(1/\epsilon))\) query complexity—exponentially better than the \(O(1/\epsilon^2)\) rate for general 2D estimation.

Proposition: Bayes Optimal Classifier from LPM

Proposition 2.4 Given learned metric weights \(\mathbf{m} = (m_{11}, m_{00})\) with \(m_{11} + m_{00} > 0\), the Bayes optimal classifier is: \[ \bar{h}(x) = \mathbf{1}\left[\eta(x) \geq \frac{m_{00}}{m_{11} + m_{00}}\right] \] where \(\eta(x) = P(Y=1 \mid X=x)\) is the conditional class probability.

This connects metric elicitation to decision theory: learning the metric \(\mathbf{m}\) is equivalent to learning the optimal classification threshold.

Extension to Linear-Fractional Metrics. The \(F_\beta\) score and Jaccard similarity are not linear but linear-fractional: \[ \phi(C) = \frac{p_{11} \cdot \text{TP} + p_{00} \cdot \text{TN} + p_0}{q_{11} \cdot \text{TP} + q_{00} \cdot \text{TN} + q_0} \] These can be elicited by first finding both the maximizer and minimizer of the implicit linear numerator (two binary searches), then solving for the fractional parameters. The query complexity remains \(O(\log(1/\epsilon))\).

Multiclass Extension. For \(K\)-class problems, diagonal linear performance metrics (DLPMs) weight correct predictions: \(\psi(\mathbf{d}) = \sum_k a_k d_k\) where \(d_k\) is the rate of correctly predicting class \(k\). Binary search over each pair of classes \((k_1, k_2)\) recovers the relative weights \(a_{k_2}/a_{k_1}\), with total complexity \(O(K^2 \log(1/\epsilon))\).

2.18 Measurement of User Preference Function

Suppose items \(j\) have feature vectors \(X_j \in \mathbb R^d\). Instead of learning a free scalar parameter \(V_j\) for each item, we assume \(V_j = W^\top X_j,\) where \(W \in \mathbb R^d\) is shared across items. The probability that item \(j\) beats item \(k\) is \(p(j \succ k) = \sigma(V_j - V_k) = \sigma (W^\top(X_j - X_k)).\) This is simply logistic regression on pairwise feature differences. Given one comparison outcome \(y \in \{0,1\}\) for pair \((j,k)\) with difference \(x_{jk} = X_j - X_k\), \[\ell(W) = y\log \sigma(W^\top x_{jk}) + (1-y)\log(1-\sigma(W^\top x_{jk})). \tag{2.33}\] Gradient: \(\nabla_W \ell = (y - p) x_{jk}, \quad p = \sigma( W^\top x_{jk} ).\) Fisher Information (expected negative Hessian): \(\mathcal I(W) = \mathbb E\big[(y-p)^2 x_{jk}x_{jk}^\top\big] = p(1-p),x_{jk}x_{jk}^\top.\)

With Gaussian prior \(W \sim \mathcal N(0,\sigma_0^2 I)\), a Laplace approximation yields posterior covariance \(\Sigma \approx (\sigma_0^{-2}I + \sum_t p_t(1-p_t) x_t x_t^\top)^{-1}.\) So, as in the Rasch case, Fisher information accumulates to form posterior precision. At each step, pick a candidate pair \((j,k)\) and compute \[ \Delta_D(j,k) = \log \det(\Lambda + w x_{jk} x_{jk}^\top) - \log\det(\Lambda), \quad w = p(1-p), \tag{2.34}\] where \(\Lambda = \Sigma^{-1}\). This is the D-optimal criterion, maximizing the expected log-determinant gain in information. A-optimal or E-optimal criteria are similarly defined. We’ll simulate item features, a ground-truth \(W\), and comparisons. Then we compare active D-optimal elicitation vs random pair selection for estimating \(W\). Performance metrics are MSE of \(\hat W\) vs true \(W\), and reliability.

First, set up the simulation with item features and ground-truth weights:

Code

Define the Fisher gain and Bayesian update functions:

Code

Run the simulation comparing D-optimal vs random selection:

Code

Visualize the results:

Code

2.18.1 Robotic Trajectory Learning

The linear preference framework applies directly to robotic trajectory learning (Biyik and Sadigh 2018). Consider a robot choosing between trajectories \(\xi_A\) and \(\xi_B\). The human evaluates them via a reward function: \[ R(\xi) = w^\top \phi(\xi) \tag{2.35}\] where \(w \in \mathbb{R}^N\) are unknown weights and \(\phi(\xi) \in \mathbb{R}^N\) extracts features (e.g., distance to lane boundaries, proximity to obstacles, heading, speed). This is exactly our linear model with “items” being trajectories and “features” being \(\phi(\xi)\).

Geometric Interpretation. Each pairwise comparison “prefer \(\xi_A\) over \(\xi_B\)” yields a constraint: \[ w^\top (\phi(\xi_A) - \phi(\xi_B)) > 0 \] This defines a half-space in the weight space. The feasible region for \(w\) is the intersection of all half-spaces consistent with observed preferences. Each query splits this region—orthogonal queries reduce volume by approximately half.

The optimal query selection criterion maximizes the minimum volume removed regardless of the oracle’s answer. For query feature difference \(\Phi = \phi(\xi_A) - \phi(\xi_B)\), this is \(\max_\Phi \min\{\mathbb{E}[1 - f_\Phi(w)], \mathbb{E}[1 - f_{-\Phi}(w)]\}\) where \(f_\Phi(w) = \min(1, \exp(w^\top \Phi))\) soft-weights consistency with the preference. This selects balanced queries where either response is informative.

Driving Simulator Example. In a 2D driving simulator, trajectory features include:

• Distance to lane boundaries
• Distance to other vehicles
• Heading angle
• Speed

With no learned preferences, the simulated car moves erratically. After 30 comparison queries, it learns to follow the lane direction. After 70 queries, it additionally learns to avoid collisions while staying in lane. The features with highest learned weights correspond to collision avoidance and lane-keeping.

Why Active Selection Matters. Both active and random query selection eventually converge to the true reward weights. However, active selection achieves target performance faster—critical in time-sensitive applications. For exoskeleton rehabilitation (Li et al. 2021), the robot must adapt to individual patients quickly; waiting for asymptotic convergence is not acceptable. Active learning provides crucial early-stage advantages.

Imitation Learning with Compatibility. When learning from multiple human demonstrators, multimodality arises: different people use different strategies for the same task (e.g., picking up an object from the left vs. right). Naive imitation learning fails on contradictory demonstrations.

The solution is to measure compatibility of new demonstrations with the base policy:

• Likelihood: How close is the demonstrated action to the base policy’s prediction?
• Novelty: How uncertain is the base policy at this state?

Demonstrations with low likelihood in low-novelty states indicate conflicting modes and should be filtered. This compatibility-based filtering improves success rates while using less data than naive aggregation (Gandhi et al. 2022).

Foundation Models for Representations. Recent work leverages foundation models pretrained on human video (R3M (Nair et al. 2022), Voltron (Karamcheti et al. 2023)) to provide better trajectory features \(\phi(\xi)\). These models learn that human hands are similar to robotic end-effectors, enabling 2-3x higher success rates with 5-10x fewer demonstrations. For preference learning, better representations mean each comparison is more informative.

2.18.2 Non-Linear Scoring Functions

So far we set \(V_j=W^\top X_j\). Suppose instead that items are scored by a non-linear function \[V_j = f_\theta(X_j),\qquad \theta\in\mathbb{R}^p, \qquad p(j \succ k) = \sigma (f_\theta(X_j) - f_\theta(X_k)) \tag{2.36}\] We want an online procedure that chooses the next comparison \((j,k)\) to learn \(\theta\) quickly. Exact Bayesian design is intractable for general \(f_\theta\). There is a simple and effective approximation that keeps all the math and code lightweight: local Gaussian posterior over \(\theta\) via Laplace + first-order model. Work at the current estimate \(\hat\theta\). Linearize the non-linear scorer around \(\hat\theta\): \[ f_\theta(X_j) \approx f_{\hat\theta}(X_j) + J_j\Delta\theta, \qquad J_j \equiv \left.\frac{\partial f_\theta(X_j)}{\partial \theta}\right| _{\theta = \hat\theta} \in \mathbb{R}^{1\times p}. \tag{2.37}\] The pairwise logit for \((j,k)\) becomes \[\underbrace{f_\theta(X_j)-f_\theta(X_k)}_{\text{logit}} \approx \underbrace{f_{\hat\theta}(X_j)-f_{\hat\theta}(X_k)}_{\text{offset}} + \underbrace{(J_j-J_k)}_{\phi_{jk}}\Delta\theta. \tag{2.38}\]

Define the local “design vector” \(\phi_{jk}\in\mathbb{R}^{1\times p}\). With a Gaussian prior \(\theta\sim\mathcal N(0,\sigma_0^2 I)\) and Bernoulli likelihood, the Laplace posterior around \(\hat\theta\) is \[ \theta \mid \mathcal D \approx \mathcal N(\hat\theta,;\Sigma),\qquad \Sigma^{-1} = \sigma_0^{-2} I + \sum_{t} w_t \phi_t^\top \phi_t \tag{2.39}\] where \(w_t = p_t(1-p_t)\) with \(p_t = \sigma\big(f_{\hat\theta}(X_{j_t})-f_{\hat\theta}(X_{k_t})\big)\). This is exactly the same structure as the linear case, with (x_{jk}) replaced by \(\phi_{jk}=J_j-J_k\). You only need Jacobian rows \(J_j\). At the current \((\hat\theta \Sigma)\) and for a candidate \((j,k)\), compute \(p=\sigma\big(f_{\hat\theta}(X_j)-f_{\hat\theta}(X_k)\big)\) and \(w = p(1-p)\).Compute \(\phi = J_j-J_k\) at \(\hat \theta\). Then use any standard optimal design score with Sherman–Morrison:

• D-optimal (log-det gain): \(\Delta_D(j,k) = \log ( 1 + w\phi \Sigma \phi^\top )\).
• A-optimal (trace drop): \(\Delta_A(j,k) = \dfrac{w \phi \Sigma^2 \phi^\top }{ 1+w \phi \Sigma \phi^\top}\).
• E-optimal proxy: \(\Delta_E^{\text{proxy}}(j,k) = w \phi \Sigma \phi^\top\).

Pick the pair with the largest gain. This is tractable because it only needs a vector–matrix–vector product with \(\Sigma\) and a Jacobian row. Mutual-information acquisition like BALD reduces to the same formulas under the Laplace Gaussian approximation. Maximizing (_D) is a good default.

We use a tiny two-layer network \(f_\theta(x)=a^\top \tanh(Bx)\) with \(\theta=(a,B)\). We derive \(J_j\) analytically. First, define the network and its Jacobian:

Set up Laplace approximation state and update functions:

Run the active learning loop comparing D-optimal vs random selection:

Visualize results:

2.19 Active Query Selection for Gaussian Process Models

The previous sections developed Fisher information for optimal query selection in parametric preference models—the Rasch model (Section 1) and linear scoring functions (Section 2). However, Chapter 2 introduced Gaussian Processes (GPs) as a flexible nonparametric alternative for reward modeling, and Chapter 3 covered GP inference via Laplace approximation. Here we address the natural question: how do we actively select queries when using GPs?

The key insight is that GP uncertainty—quantified by the posterior variance—naturally guides query selection. Unlike parametric models where Fisher information depends only on the current parameter estimate, GP uncertainty varies across the input space, being higher far from observed data and lower near it.

2.19.1 Information-Theoretic Acquisition Function

For GP preference learning, we seek queries that maximize information gain about the reward function. Given a dataset \(\mathcal{D}\) and a candidate query \(Q = (x_A, x_B)\), the acquisition function measures the expected reduction in uncertainty about \(r\): \[ a(Q) = I(r; y \mid \mathcal{D}, Q) = H(y \mid \mathcal{D}, Q) - \mathbb{E}_{r \sim p(r \mid \mathcal{D})}[H(y \mid r, Q)] \tag{2.40}\]

Interpretation of the two terms:

1. \(H(y \mid \mathcal{D}, Q)\): Predictive entropy—how uncertain is the query outcome under our current model? High when \(p(A \succ B) \approx 0.5\).

2. \(\mathbb{E}_r[H(y \mid r, Q)]\): Expected conditional entropy—how uncertain would the query be if we knew the true reward function? Low for “easy” comparisons, high for inherently noisy comparisons.

The acquisition function trades off these two terms: we want queries where the model is uncertain (high predictive entropy) but a human could provide a clear answer (low expected conditional entropy).

2.19.2 Practical Computation

Using the Laplace approximation from Chapter 3 (Section 2.4.2), the acquisition function can be computed as: \[ a(x_A, x_B) = h\left(\Phi\left(\frac{\mu_A - \mu_B}{\sqrt{2\sigma_{\text{noise}}^2 + g(x_A, x_B)}}\right)\right) - m(x_A, x_B) \tag{2.41}\]

where: - \(\mu_A, \mu_B\) are the GP posterior means at \(x_A, x_B\) - \(g(x_A, x_B) = \sigma_A^2 + \sigma_B^2 - 2\text{Cov}(r(x_A), r(x_B))\) captures uncertainty from both points - \(h(p) = -p\log_2 p - (1-p)\log_2(1-p)\) is binary entropy - \(\Phi\) is the standard normal CDF - \(m(x_A, x_B)\) is a correction term for human noise

Key property: The trivial query \(Q = (x, x)\) (comparing an item to itself) is a global minimizer, not maximizer, of this acquisition function. This contrasts with some other methods that can get stuck on uninformative queries.

First, we define the RBF kernel and helper functions for the simulation:

Next, we implement a GP model for active preference learning. The fit method uses Laplace approximation (Newton’s method) to find the posterior mode, and acquisition computes the information gain for a candidate query:

Now we run the simulation, comparing active (information-theoretic) query selection against random selection:

Finally, we visualize the results. The left panel shows how estimation error decreases with more comparisons; the right panel shows the learned reward functions:

2.19.3 When to Use GP Active Learning

Scenario	Recommendation
Nonlinear reward structure	GP strongly preferred
Low-to-moderate dimensions (\(d \lesssim 10\))	GP works well
Expensive human feedback	Active learning essential
Need uncertainty quantification	GP provides this naturally
Large datasets (\(n > 1000\))	Consider sparse GP approximations
Very high dimensions	Linear models may be more practical

2.20 Active Learning for Direct Preference Optimization

We now turn to a specific, important application: active learning for DPO (Direct Preference Optimization) in large language model alignment. Chapter 2 introduced DPO and its connection to Bradley-Terry; here we show how to apply active learning principles to reduce the number of human comparisons needed.

2.20.1 The DPO Setting

Recall from Section 1.2 that DPO directly optimizes a policy \(\pi_\theta\) on preference data without learning an explicit reward model. The key insight is that DPO implicitly assumes Bradley-Terry preferences: \[ p(y_w \succ y_l \mid x) = \sigma\left(\beta \log \frac{\pi_\theta(y_w \mid x)}{\pi_{\text{ref}}(y_w \mid x)} - \beta \log \frac{\pi_\theta(y_l \mid x)}{\pi_{\text{ref}}(y_l \mid x)}\right) \tag{2.42}\]

Challenge: Large language models have billions of parameters, making exact Fisher information computation intractable. How can we apply the D-optimal design principles from Sections 1-2?

2.20.2 The Log-Linear Policy Assumption

The key insight is to approximate the policy as log-linear in the last-layer features: \[ \pi(y \mid x; \theta) \propto \exp(\phi(x, y)^\top \theta) \tag{2.43}\]

where \(\phi(x, y)\) is the feature representation from the model’s last layer. This assumption is justified by the neural tangent kernel perspective: for sufficiently large networks, the dynamics during training are approximately linear in the parameters.

Under this assumption, the DPO loss Hessian takes the form: \[ H(\theta) = \sum_{i=1}^n p_i(1-p_i) \cdot \Delta\phi_i \Delta\phi_i^\top \tag{2.44}\]

where \(\Delta\phi_i = \phi(x_i, y_{w,i}) - \phi(x_i, y_{l,i})\) is the feature difference between winning and losing responses, and \(p_i\) is the predicted preference probability.

Key observation: This Hessian is exactly the Fisher information matrix for the DPO model! The D-optimal criterion becomes: \[ \max_S \log\det\left(\sum_{i \in S} p_i(1-p_i) \cdot \Delta\phi_i \Delta\phi_i^\top\right) \tag{2.45}\]

2.20.3 The ADPO Algorithm

The Active DPO (ADPO) algorithm applies D-optimal design to select preference comparisons:

Algorithm: Active DPO (ADPO)

Input: Reference policy \(\pi_{\text{ref}}\), prompt set \(\{x_i\}\), response pairs \(\{(y_{i,1}, y_{i,2})\}\), budget \(T\)

Initialize: \(\theta_0 = \theta_{\text{ref}}\), \(S_0 = \emptyset\)

For \(t = 1, \ldots, T\):

1. Compute features: For each candidate pair \((x_i, y_{i,1}, y_{i,2})\):

   • \(\Delta\phi_i = \phi(x_i, y_{i,1}) - \phi(x_i, y_{i,2})\)
   • \(p_i = \sigma(\beta(\log\pi_{\theta_{t-1}}(y_{i,1}|x_i) - \log\pi_{\theta_{t-1}}(y_{i,2}|x_i)))\)

2. D-optimal selection: Select query maximizing: \[i^* = \arg\max_i \log\det\left(I + p_i(1-p_i) H_t^{-1} \Delta\phi_i \Delta\phi_i^\top\right) \tag{2.46}\] where \(H_t\) is the current Fisher information matrix

3. Query oracle: Obtain human preference \(y_t\) for pair \((x_{i^*}, y_{i^*,1}, y_{i^*,2})\)

4. Update: \(S_t = S_{t-1} \cup \{(i^*, y_t)\}\), retrain \(\theta_t\) on \(S_t\) using DPO loss

Return: Final policy \(\pi_{\theta_T}\)

When the Log-Linear Policy Assumption Fails

ADPO’s theoretical guarantees rely on the log-linear policy assumption: that \(\log \pi_\theta(y \mid x)\) is approximately linear in \(\theta\), which holds in the neural tangent kernel (NTK) regime near the reference policy. This approximation degrades when: (1) the policy is fine-tuned far from the reference (large \(\|\theta - \theta_{\text{ref}}\|\)), (2) the model is small relative to the data complexity so the NTK regime does not hold, or (3) the loss landscape is highly non-convex with multiple basins. In these settings, the Fisher information computed under the log-linear assumption may poorly reflect the actual curvature of the loss, leading to suboptimal query selection. Practitioners should monitor whether the D-optimal gains predicted by the linear model correlate with actual improvements in policy quality.

2.20.4 Theoretical Guarantees

Under standard regularity conditions, ADPO achieves the following convergence rate:

Theorem: ADPO Convergence Rate

Theorem 2.1 Let \(\theta^*\) be the optimal policy parameters. Under the log-linear policy assumption and standard regularity conditions, ADPO with \(n\) actively selected comparisons achieves: \[ \|\hat\theta_n - \theta^*\| = O\left(\frac{d}{\sqrt{n}}\right) \tag{2.47}\] where \(d\) is the effective dimension (rank of the Fisher information matrix). This matches the minimax optimal rate for \(d\)-dimensional estimation.

The key insight is that D-optimal design ensures the Fisher information grows proportionally to \(n\), leading to \(O(1/\sqrt{n})\) estimation error.

2.20.5 ADPO+ for Offline Settings

In many practical settings, we have access to a fixed pool of unlabeled preference pairs (e.g., model outputs) but cannot generate new queries. ADPO+ adapts the algorithm for this offline setting:

1. Pool-based selection: Instead of synthesizing queries, select from the existing pool
2. Batch selection: Select \(b\) queries at once to enable parallel annotation
3. Diversity regularization: Add penalty for selecting similar queries

The D-optimal criterion naturally encourages diversity: selecting redundant queries provides diminishing information gain.

2.20.6 Empirical Guidance: When Does Active Learning Help?

Factor	Active Learning Beneficial?
Annotation cost	High cost → Active learning essential
Data heterogeneity	Diverse prompts → More room for strategic selection
Budget constraints	Limited budget → Active learning shows larger gains
Model capacity	Larger models → Active learning helps reduce overfitting
Query pool size	Large pool → More room for intelligent selection

Practical recommendation: Active learning for DPO provides the largest gains when: - Annotation budget is limited (< 10K comparisons) - Prompts cover diverse topics or difficulty levels - The goal is sample efficiency over raw performance

Comparison: GP Active Learning vs. ADPO

Aspect	GP Active Learning	ADPO
Model	Nonparametric (GP)	Parametric (neural network)
Scalability	\(O(n^3)\)	\(O(d^2 n)\) with approximations
Use case	Small datasets, need uncertainty	LLM alignment, large models
Acquisition	Information gain	D-optimal design
Theoretical basis	Mutual information	Fisher information

Both approaches share the core insight: use model uncertainty to guide query selection.

2.21 Summary

• When human feedback is expensive, which comparisons to request matters as much as how to learn from them. This chapter develops the theory of optimal query selection for preference learning.
• Fisher information \(\mathcal{I}_j(U) = p(1-p)\) quantifies how much a single comparison reveals about user preferences. Items with predicted win probability \(p \approx 0.5\) are most informative—close competitions reveal more than blowouts.
• Three optimal design criteria guide query selection: A-optimal (minimize average variance), D-optimal (maximize the determinant of the information matrix, shrinking the posterior ellipsoid’s volume), and E-optimal (minimize the worst-case variance).
• For multi-dimensional preferences, the Sherman-Morrison update enables efficient \(O(K^2)\) covariance updates after each query, making real-time active selection practical.
• Gaussian Process active learning extends these ideas to nonparametric models using information-theoretic acquisition functions—selecting queries that maximize mutual information between the response and the latent preference function.
• Active DPO (ADPO) applies D-optimal design to language model alignment, using a log-linear approximation to make Fisher information computation tractable for billion-parameter models. ADPO achieves the minimax-optimal convergence rate \(O(d/\sqrt{n})\).
• Across all settings—scalar preferences, factor models, GPs, and LLMs—the core insight is the same: use model uncertainty to guide query selection, focusing annotation effort where it reduces uncertainty most.

2.22 Quick Check

Test your understanding before proceeding to the exercises.

1. An item has predicted success probability \(p = 0.95\). What is its Fisher information \(\mathcal{I} = p(1-p)\)? Would you select this item for active learning? Why or why not?

2. A-optimal design minimizes the average posterior variance; D-optimal minimizes the volume of the confidence ellipsoid. In what situation would these select different items?

3. In ADPO, why is the log-linear policy assumption (\(\pi(y|x;\theta) \propto \exp(\phi(x,y)^\top \theta)\)) important? What would happen without it?

Essential Reading

If you read only five papers from this chapter’s references, make them these:

1. Rasch (1960) — The Rasch model: foundational psychometric model connecting item difficulty to person ability
2. Fedorov (1972) — The theory of optimal experimental design (A/D/E-optimality)
3. Chu and Ghahramani (2005) — Gaussian process preference learning: nonparametric Bayesian approach to utility functions
4. Houlsby et al. (2011) — Bayesian active learning by disagreement (BALD), connecting information gain to query selection
5. Christiano et al. (2017) — Deep RL from human preferences: the original active elicitation pipeline for reward learning

2.23 Discussion Questions

1. How does the reliability metric defined in this chapter relate to classical test theory in psychometrics? What assumptions underlie this correspondence?

2. Why does D-optimal design maximize the log-determinant of the information matrix rather than the trace? In what situations might A-optimal (trace-based) selection be preferable?

3. The local linearization approach for non-linear scoring functions trades off accuracy for tractability. What are the conditions under which this approximation is most accurate? When might it fail?

4. Active preference learning assumes that items’ appeals are known or pre-calibrated. How might estimation errors in item parameters affect the efficiency of active selection strategies?

5. The metric elicitation framework assumes an oracle with a consistent underlying preference. How would you modify the approach to handle an oracle whose preferences evolve over time or exhibit inconsistencies?

6. In the robotics case studies, pairwise comparisons are used to learn reward functions. What are the advantages and disadvantages of pairwise comparisons versus direct reward labeling for robotic learning?

7. Foundation models like R3M and Voltron leverage pretraining on human video data. What types of robotic tasks might benefit most from this approach? What tasks might still require substantial robot-specific data?

8. The active elicitation framework for imitation learning identifies “compatible” demonstrations. How might this concept of compatibility be extended to multi-agent settings where different agents have legitimately different optimal behaviors?

2.24 Further Reading

For readers who want to go deeper into the topics introduced in this chapter, we recommend the following:

• Fedorov (1972), Theory of Optimal Experiments — The classical reference on A/D/E-optimal experimental design, providing the mathematical foundations for the Fisher information-based query selection methods used throughout this chapter.
• Chaloner and Verdinelli (1995), “Bayesian Experimental Design: A Review” — A unified information-theoretic approach to experimental design that extends the Fisher information framework to Bayesian settings, including mutual information-based criteria that are robust to model misspecification.
• Settles (2012), Active Learning — A comprehensive survey of active learning, covering pool-based, stream-based, and query-synthesis approaches. Places the preference elicitation methods in this chapter within the broader active learning literature.
• Linden and Glas (2010), Elements of Adaptive Testing — How Fisher information drives modern standardized testing (GRE, GMAT), providing the practical context for the Rasch model-based elicitation methods discussed in this chapter.
• Houlsby et al. (2011), “Bayesian Active Learning for Classification and Preference Learning” — Introduces the BALD (Bayesian Active Learning by Disagreement) acquisition function, an information-theoretic alternative to D-optimal design that works well with GP models.
• Sadigh et al. (2017), “Active Preference-Based Learning of Reward Functions” — Active query selection for robot trajectory preferences, demonstrating how the Fisher information framework applies to continuous, high-dimensional preference learning in robotics.
• Hiranandani et al. (2019), “Multiclass Performance Metric Elicitation” — The paper behind the metric elicitation case study, showing how active preference queries can recover a practitioner’s implicit loss function for classifier evaluation.

2.25 Exercises

We place (*), (**), and (***) for exercises we deem relatively easy, medium, and hard.

2.25.1 Fisher Information Maximum (*)

Show that for the Rasch model with \(p = \sigma(U + V_j)\), the Fisher information \(\mathcal{I}_j(U) = p(1-p)\) is maximized when \(p = 0.5\). What does this imply about the optimal difficulty of items for measuring a user’s ability?

2.25.2 Sherman-Morrison Update (**)

Derive the Sherman-Morrison formula for efficiently updating the posterior covariance when adding a single rank-1 observation. Specifically, show that if \(\Sigma^{-1} \gets \Sigma^{-1} + w \cdot vv^\top\), then \(\Sigma \gets \Sigma - \frac{w \cdot \Sigma vv^\top \Sigma}{1 + w \cdot v^\top \Sigma v}\).

2.25.3 D-Optimal vs A-Optimal (**)

Construct a 2D example where D-optimal and A-optimal criteria select different items for the next query. Interpret the difference geometrically in terms of the posterior ellipsoid.

2.25.4 Pairwise Fisher Information (**)

For the Bradley-Terry model \(p(j \succ k | U) = \sigma(U^\top(V_j - V_k))\), derive the Fisher information matrix for \(U\) given a single pairwise comparison. How does this relate to the single-item case?

2.25.5 Active Selection Implementation (***)

Extend the D-optimal pairwise selection simulation to include all three optimality criteria (A, D, E). Compare their sample efficiency on a synthetic dataset of 50 items with 3-dimensional user preferences. Which criterion performs best under different prior uncertainty structures?

2.25.6 Noisy Oracle Elicitation (***)

Extend the LPM elicitation algorithm to handle noisy oracle responses where the oracle flips its answer with probability \(\epsilon < 0.5\). How does the query complexity scale with \(\epsilon\)?

2.25.7 Local Linearization Analysis (***)

Consider a scoring function \(f_\theta(x) = a^\top \tanh(Bx)\) with \(\theta = (a, B)\). Analytically derive the Jacobian \(J_j = \partial f_\theta(X_j) / \partial \theta\). Under what conditions on the hidden activations \(\tanh(BX_j)\) is the local Gaussian approximation most accurate?

2.25.8 Compatibility Metric Design (**)

In the active elicitation framework for imitation learning, the compatibility metric depends on thresholds \(\lambda\) and \(\eta\). Design an algorithm that automatically selects these thresholds from a held-out validation set of demonstrations. What objective should the algorithm optimize?

References

Agresti, Alan. 2002. Categorical Data Analysis. 2nd ed. New York: John Wiley & Sons.

al., Yuntao Bai et. 2022. “Constitutional AI: Harmlessness from AI Feedback.” https://arxiv.org/abs/2212.08073.

Bergmeir, Christoph, Rob J. Hyndman, and Bonsoo Koo. 2018. “A Note on the Validity of Cross-Validation for Evaluating Autoregressive Time Series Prediction.” Computational Statistics & Data Analysis 120: 70–83.

Biyik, Erdem, and Dorsa Sadigh. 2018. “Batch Active Preference-Based Learning of Reward Functions.” In Proceedings of the 2nd Conference on Robot Learning, edited by Aude Billard, Anca Dragan, Jan Peters, and Jun Morimoto, 87:519–28. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v87/biyik18a.html.

Boyd, Stephen, and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press.

Bradley, Ralph Allan, and Milton E Terry. 1952. “Rank Analysis of Incomplete Block Designs: I. The Method of Paired Comparisons.” Biometrika 39 (3/4): 324–45.

Caron, François, and Arnaud Doucet. 2012. “Efficient Bayesian Inference for Generalized Bradley-Terry Models.” Journal of Computational and Graphical Statistics 21 (1): 174–96.

Cawley, Gavin C., and Nicola L. C. Talbot. 2010. “On over-Fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation.” Journal of Machine Learning Research 11: 2079–2107.

Chaloner, Kathryn, and Isabella Verdinelli. 1995. “Bayesian Experimental Design: A Review.” Statistical Science 10 (3): 273–304.

Christiano, Paul F, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. 2017. “Deep Reinforcement Learning from Human Preferences.” Advances in Neural Information Processing Systems 30.

Chu, Wei, and Zoubin Ghahramani. 2005. “Preference Learning with Gaussian Processes.” Proceedings of the 22nd International Conference on Machine Learning, 137–44.

Davidson, Roger R. 1970. “On Extending the Bradley-Terry Model to Accommodate Ties in Paired Comparison Experiments.” Journal of the American Statistical Association 65 (329): 317–28.

Elo, Arpad E. 1978. The Rating of Chessplayers, Past and Present. New York: Arco Publishing.

Fedorov, Valerii V. 1972. Theory of Optimal Experiments. Academic Press.

Ford Jr, Lester R. 1957. “Solution of a Ranking Problem from Binary Comparisons.” The American Mathematical Monthly 64 (8P2): 28–33.

Gandhi, Kanishk, Siddharth Karamcheti, Madeline Liao, and Dorsa Sadigh. 2022. “Eliciting Compatible Demonstrations for Multi-Human Imitation Learning.” In Proceedings of the 6th Conference on Robot Learning (CoRL).

Gao, Leo, John Schulman, and Jacob Hilton. 2022. “Scaling Laws for Reward Model Overoptimization.” arXiv Preprint arXiv:2210.10760.

Geisser, Seymour. 1975. “The Predictive Sample Reuse Method with Applications.” Journal of the American Statistical Association 70 (350): 320–28.

Geman, Stuart, Elie Bienenstock, and Rene Doursat. 1992. “Neural Networks and the Bias/Variance Dilemma.” Neural Computation 4 (1): 1–58.

Glickman, Mark E. 1999. “Parameter Estimation in Large Dynamic Paired Comparison Experiments.” Journal of the Royal Statistical Society: Series C (Applied Statistics) 48 (3): 377–94. https://doi.org/10.1111/1467-9876.00159.

Gneiting, Tilmann, and Adrian E Raftery. 2007. “Strictly Proper Scoring Rules, Prediction, and Estimation.” Journal of the American Statistical Association 102 (477): 359–78.

Hastie, Trevor, Robert Tibshirani, and Jerome Friedman. 2009. The Elements of Statistical Learning: Data Mining, Inference and Prediction. 2nd ed. New York: Springer.

Herbrich, Ralf, Tom Minka, and Thore Graepel. 2006. “TrueSkill: A Bayesian Skill Rating System.” In Advances in Neural Information Processing Systems, 19:569–76.

Hiranandani, Gaurush, Shant Boodaghians, Ruta Mehta, and Oluwasanmi Koyejo. 2019. “Performance Metric Elicitation from Pairwise Classifier Comparisons.” In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, edited by Kamalika Chaudhuri and Masashi Sugiyama, 89:371–79. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v89/hiranandani19a.html.

Hoerl, Arthur E., and Robert W. Kennard. 1970. “Ridge Regression: Biased Estimation for Nonorthogonal Problems.” Technometrics 12 (1): 55–67.

Houlsby, Neil, Ferenc Huszár, Zoubin Ghahramani, and Máté Lengyel. 2011. “Bayesian Active Learning for Classification and Preference Learning.” In arXiv Preprint arXiv:1112.5745.

Hunter, David R. 2004. “MM Algorithms for Generalized Bradley-Terry Models.” The Annals of Statistics 32 (1): 384–406. https://doi.org/10.1214/aos/1079120141.

Karamcheti, Siddharth et al. 2023. “Language-Driven Representation Learning for Robotics.” arXiv Preprint arXiv:2302.12766.

Kingma, Diederik P., and Jimmy Ba. 2014. “Adam: A Method for Stochastic Optimization.” arXiv Preprint arXiv:1412.6980.

Kohavi, Ron. 1995. “A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection” 14 (2): 1137–45.

Koren, Yehuda, Robert Bell, and Chris Volinsky. 2009. “Matrix Factorization Techniques for Recommender Systems.” Computer 42 (8): 30–37.

Li, Kejun, Maegan Tucker, Erdem Biyik, Ellen Novoseller, Joel W. Burdick, Yanan Sui, Dorsa Sadigh, Yisong Yue, and Aaron D. Ames. 2021. “ROIAL: Region of Interest Active Learning for Characterizing Exoskeleton Gait Preference Landscapes.” In 2021 IEEE International Conference on Robotics and Automation (ICRA). IEEE. https://doi.org/10.1109/icra48506.2021.9560840.

Linden, Wim J. van der, and Cees A. W. Glas. 2010. Elements of Adaptive Testing. New York: Springer.

Liu, Tie-Yan. 2011. Learning to Rank for Information Retrieval. Springer.

Loshchilov, Ilya, and Frank Hutter. 2016. “SGDR: Stochastic Gradient Descent with Warm Restarts.” arXiv Preprint arXiv:1608.03983.

Marden, John I. 1995. Analyzing and Modeling Rank Data. Chapman & Hall.

Murphy, Kevin P. 2012. Machine Learning: A Probabilistic Perspective. Cambridge, MA: MIT Press.

Nair, Suraj, Aravind Rajeswaran, Vikash Kumar, Chelsea Finn, and Abhinav Gupta. 2022. “R3M: A Universal Visual Representation for Robot Manipulation.” https://arxiv.org/abs/2203.12601.

Ouyang, Long, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, et al. 2022. “Training Language Models to Follow Instructions with Human Feedback.” Advances in Neural Information Processing Systems 35: 27730–44.

Rafailov, Rafael, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D. Manning, and Chelsea Finn. 2023. “Direct Preference Optimization: Your Language Model Is Secretly a Reward Model.” https://arxiv.org/abs/2305.18290.

Rasch, Georg. 1960. Probabilistic Models for Some Intelligence and Attainment Tests. Danish Institute for Educational Research.

Rasmussen, Carl Edward, and Christopher K. I. Williams. 2006. Gaussian Processes for Machine Learning. Cambridge, MA: MIT Press.

Ruder, Sebastian. 2016. “An Overview of Gradient Descent Optimization Algorithms.” arXiv Preprint arXiv:1609.04747.

Sadigh, Dorsa, Anca D Dragan, Shankar Sastry, and Sanjit A Seshia. 2017. “Active Preference-Based Learning of Reward Functions.” In Robotics: Science and Systems.

Settles, Burr. 2012. Active Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers.

Stiennon, Nisan, Long Ouyang, Jeff Wu, Daniel M. Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul Christiano. 2020. “Learning to Summarize from Human Feedback.” Advances in Neural Information Processing Systems 33.

Stone, M. 1974. “Cross-Validatory Choice and Assessment of Statistical Predictions.” Journal of the Royal Statistical Society: Series B (Methodological) 36 (2): 111–33. https://doi.org/10.1111/J.2517-6161.1974.TB00994.X.

Weng, Ruby C., and Chih-Jen Lin. 2011. “A Bayesian Approximation Method for Online Ranking.” Journal of Machine Learning Research 12: 267–300.

Yao, Yuan, Lorenzo Rosasco, and Andrea Caponnetto. 2007. “On Early Stopping in Gradient Descent Learning.” Constructive Approximation 26 (2): 289–315.