Mathematical Foundations of AI Alignment, Lecture 5.2 (Maximal Lotteries and No Regret Learning P2)

Overview

Aaron Roth connects maximal lotteries to von Neumann’s minimax theorem using Hedge and no-regret learning. In an antisymmetric preference game, the game’s value is zero, so a lottery exists that no competing distribution can strictly defeat; averaging strategies from self-play produces an approximately maximal lottery when realized regret is low. Roth then derives a practical RLHF-inspired recipe that trains a language model using pairwise comparisons between completions sampled from its current policy, while noting that its guarantee depends on the training procedure’s regret.

Key takeaways

For an antisymmetric preference matrix M, the zero-sum game has value zero because either player can copy the other’s lottery; minimax equality therefore guarantees a distribution that no challenger can strictly defeat.
Hedge proves von Neumann’s minimax theorem constructively: repeated best responses yield an average payoff bounded below by the minimax value and above by the maximin value plus average regret.
In self-play on an antisymmetric game, the learner’s realized payoff is always zero, so a no-regret bound directly limits how much any fixed challenger can exploit the learner’s time-average strategy.
The average of a no-regret learner’s strategies has exploitability at most its realized regret divided by the number of rounds, even when the learner is not literally Hedge.
A scalable language-model adaptation can reward each sampled completion by its expected pairwise margin against other completions sampled from the same current policy, avoiding an exact best-response oracle.
The practical RLHF-style recipe is conditional rather than universally guaranteed: its maximality claim depends on low realized regret and on the comparator class covered by that regret.

Chapters

0:00 Preference Cycles Motivate Maximal Lotteries

Three outcomes can form a majority cycle: two-thirds prefer B to A, C to B, and A to C.
Choosing any single deterministic completion leaves it vulnerable to a majority-preferred alternative.
Roth proposes randomization: a uniform lottery over A, B, and C cannot be strictly beaten by another distribution over those options.

3:19 Margin Matrices Formalize Pairwise Preferences

The margin matrix M records how often outcome i beats outcome j, rescaled to values from -1 to 1.
Antisymmetry means Mᵢⱼ = -Mⱼᵢ, making self-comparisons have zero expected margin.
To compare lotteries P and Q, sample one outcome from each and an evaluator; the expected margin is pᵀMq.

5:59 Maximal Lotteries as Robust Max-Min Policies

A maximal lottery is a distribution that cannot be strictly defeated after a competitor sees it.
The policy chooses P to maximize its minimum expected margin pᵀMq over every challenger distribution Q.
A challenger can always copy P and tie, so the attainable goal is to defeat or tie every alternative, not to beat every competitor strictly.

9:08 Von Neumann Minimax and the Order of Play

Roth models the competition as a zero-sum matrix game, with one player maximizing expected payoff and the other minimizing it.
The maximin value lets the maximizer move first; the minimax value lets the minimizer move first.
Von Neumann’s minimax theorem says these values are equal for finite zero-sum games with randomized strategies, though the result need not hold for non-zero-sum games or without randomization.

15:13 Hedge Regret as the Proof’s Core Tool

Hedge maintains weights over actions and updates them by reducing the weights of actions with higher loss.
Normalizing the weights gives the distribution played each round; the guarantee compares cumulative loss with the best fixed action in hindsight.
The regret grows sublinearly, typically on the order of √T, so average regret approaches zero as the number of rounds T grows.

23:27 Turn Hedge into a Repeated Zero-Sum Game

The minimax proof imagines Min repeatedly using Hedge to choose a distribution, then revealing it to Max.
Max best-responds each round, and Min receives a loss vector whose entries are the expected game losses for each of her actions.
The round’s expected loss to Min equals the game payoff, allowing Hedge’s regret guarantee to analyze the repeated game.

27:00 Best Responses Give a Lower Bound by the Minimax Value

Because Max best-responds to Min’s distribution every round, his payoff is at least what he could guarantee against Min’s optimal strategy.
That benchmark is the minimax value, so each round’s payoff, and therefore the average payoff, is at least the minimax value.
This first bound follows directly from the order of play in the repeated-game construction.

30:19 Hedge’s Regret Closes the Minimax Gap

Hedge’s guarantee upper-bounds Min’s average loss by the loss of her best fixed distribution in hindsight, plus regret.
Averaging Max’s responses over T rounds produces a single distribution, so linearity turns the hindsight benchmark into a one-shot game against that average.
The average payoff is at most the maximin value plus regret divided by T; since average regret tends to zero, the minimax and maximin values must be equal.

39:00 The Minimax Proof Establishes an Average, Not Every Round

The proof bounds average payoff across rounds, not the payoff or strategy quality at any specific round.
Any algorithm with sublinear regret can establish the same theorem, even if it makes poor choices on a sublinear number of rounds.
The argument’s generality comes from needing only a regret guarantee, not Hedge’s specific update rule.

41:36 Antisymmetry Makes the Preference Game’s Value Zero

In the preference game, the payoff matrix is the antisymmetric margin matrix, and every distribution played against itself yields zero payoff.
Either player can copy the opponent’s lottery, giving the maximin value an upper bound of zero and the minimax value a lower bound of zero.
With minimax equality, the game’s value is exactly zero, establishing that some lottery cannot be strictly defeated.

46:50 Defining and Computing a Maximal Lottery

A maximal lottery is a distribution that wins or ties against every other distribution.
For a finite action set, a linear program can compute an optimal strategy, but the minimax theorem is what establishes that the preference-game value is zero.
The constructive proof also points toward algorithms for finding approximate strategies without relying only on an existence argument.

50:30 Average Best Responses to Build an Approximate Strategy

Run Hedge for T rounds, let Max best-respond to Min’s Hedge distribution each round, and output the uniform average of Max’s responses.
The proof implies that no challenger can beat this average strategy by more than Hedge’s average regret.
Increasing T reduces the exploitability bound, turning the minimax proof into a constructive approximation method.

55:20 Why Language-Model Training Cannot Simply Use Hedge

A literal Hedge implementation would need explicit weights over completions for every prompt, which is not scalable for language models.
Roth argues that a practical differentiable optimizer might substitute for Hedge if it achieves low regret on the losses it actually encounters.
Computing an exact best response is the larger obstacle: it can require finding the best completion across an enormous response space.

1:04:17 Self-Play Removes the Best-Response Oracle

In an antisymmetric preference game, a distribution played against itself always earns zero margin.
Instead of finding a best response, let a single no-regret learner treat its opponent as a copy of its own current distribution.
The learner still updates action weights because individual actions can have different losses, even though the played distribution’s expected self-play payoff is zero.

1:10:09 Low Regret Guarantees Low Exploitability in Self-Play

Since self-play gives the learner zero payoff each round, its regret bound limits how much better any fixed challenger could have done against the sequence.
Linearity makes that sequence equivalent to play against the time-average of the learner’s distributions.
The average policy’s exploitability, the margin by which its strongest challenger can beat it, is bounded by realized regret divided by T.

1:17:05 RLHF-Style Updates from Policy-Sampled Comparisons

For each prompt, sample multiple completions from the current language-model policy and compare the sampled completions pairwise.
Use each completion’s estimated expected margin against another completion sampled from the same policy as its reward signal.
Apply a gradient-descent-style update to the model parameters and repeat; the method avoids computing best completions or best responses.

1:22:45 Regret Scope, Human Labels, and Pairwise Reward Models

The practical recipe has no general worst-case guarantee for neural-network training; its conclusion depends on low realized regret along the training trajectory.
A regret guarantee applies only relative to the comparator class it covers, so low regret on a bounded completion set does not establish maximality over every imaginable completion.
Human evaluators can label sampled pairs, while a reward model for this method should predict a pairwise population margin from -1 to 1 rather than score one completion in isolation.

Transcript excerpt

0:12 Right. So today I want to finish up the line of thought we began last time thinking about maximal lotteryies. to briefly sort of recap um what the issue is and the proposed fix that we had. Um you know so sort of the thing that we don't want to happen is that we should deploy say some language model that gives some distribution over and then have somebody else immediately be able to say here's a better one. How do I know it's better? Well, I've pulled people and twothirds of people say that it's better. And reason why it is not immediately obvious

1:02 that we can avoid this sort of unfortunate situation is exactly this cyclic set of preferences that we've seen, you know, repeatedly now in this class. um we can have a population each of which has coherent preferences that results in you know like three outcomes A and B and C that has the property that um you know if I deploy A twothirds of people will agree that B is better if I deploy B two/3s of the people will agree that um C is better but if I deploy C like twothirds of the people will agree that A is better. So there's kind of no way and like this is just a set of preferences. So it's not a matter of

1:51 picking which of [laughter] these three completions to use. It's you know seems like sort of just a fundamental obstacle and you know this is it kind of yeah so like our hailmary attempt to get around this problem is to use randomization. So we sort of noted that like for this particular set of preferences the cycle is actually not such a big deal because we could um deploy a policy that

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

Related notes

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Aaron Roth.