Mathematical Foundations of AI Alignment, Lecture 8 (Blackwell Approachability)

Overview

Aaron Roth develops Blackwell approachability as a vector-valued generalization of the minimax theorem for repeated adversarial games. By projecting the current average outcome onto a convex target set, reducing each round to a scalar zero-sum game, and applying minimax, the learner can approach any response-satisfiable set with expected squared distance at most 4G²/t. Roth applies the method to online decision calibration: forecasts from a finite η-net achieve calibration error on the order of √(8/t) + η, supporting low swap regret for multiple downstream decision makers at once.

Key takeaways

Blackwell approachability converts a response-satisfiable vector constraint into an online guarantee by projecting the running average onto a convex set and solving a scalar minimax game defined by the projection normal.
For bounded vector increments of scale G, the approachability strategy achieves expected squared distance at most 4G²/t, so Euclidean distance shrinks at a 1/√t rate.
Decision calibration can be represented by concatenating outcome-minus-forecast residuals for each downstream action; controlling this vector controls swap regret, with a √K conversion from concatenated norm to the sum of K block norms.
Randomized forecasts are necessary against an adaptive adversary: the adversary sees the distribution over forecasts before acting, but not the sampled forecast.
Restricting forecasts to a finite η-net enables minimax while adding an η discretization term; in Roth's calibration application, the squared-distance guarantee is 8/t and calibration error is on the order of √(8/t) + η.
The vector objective can include separate bias blocks for many decision makers, allowing one forecasting system to provide decision-calibrated forecasts and low swap regret simultaneously across different utility functions.

Chapters

0:00 Decision Calibration Motivates Blackwell Approachability

Aaron Roth recaps decision calibration as a trustworthy interface between forecasts and downstream decisions.
Blackwell approachability will provide an online method for satisfying many constraints under adversarial outcomes, rather than optimizing one scalar objective.

4:00 Action-Conditional Bias Defines Decision Calibration

A forecaster issues a probability distribution over outcomes, and a decision maker chooses the action maximizing expected utility under that forecast.
For each action, decision calibration measures the difference between observed outcome frequencies and forecast probabilities on rounds when that action was chosen.

9:00 Randomized Forecasts Protect Against Adaptive Adversaries

A forecast affects both which action-specific bias bucket is updated and the residual added to that bucket, creating a coupled control problem.
The learner commits to a distribution over forecasts before the adversary chooses an outcome, then samples and reveals an actual forecast; this prevents the adversary from conditioning on the realized random choice.

14:00 Concatenating Action Biases Creates a Vector Objective

Each round contributes the outcome-minus-forecast residual to the block for the downstream action taken, with all other action blocks set to zero.
Concatenating the blocks creates a vector of dimension d times the number of actions, whose time average captures every action-conditional bias.

19:00 Calibration Error Controls Swap Regret

The sum of the norms of the action-conditional bias vectors bounds the downstream decision maker's swap regret.
Controlling the norm of the concatenated vector is sufficient up to a factor of √K, where K is the number of actions, by the Cauchy-Schwarz inequality.

24:00 Finite Forecast Nets Make Minimax Applicable

The learner's forecast actions are restricted to a finite η-net of probability distributions so finite-game minimax can be used.
A finer net reduces discretization error η, while its size can grow substantially without changing the approachability argument.

29:00 Blackwell Approachability as a Vector Game

The general game has learner actions X, adversary actions Y, and a vector-valued outcome function G(x,y) in an m-dimensional space.
The learner announces a mixed strategy first; the adversary observes that distribution but not its sampled action before choosing a response.

37:00 Response Satisfiability Reverses the Order of Play

A convex target set C is response satisfiable when, for every adversary mixed strategy, the learner can respond with a mixed strategy whose expected outcome lies in C.
Blackwell approachability uses this favorable reverse-order condition to construct a repeated-play strategy even though the learner must actually move first.

42:00 The Minimax Analogy and Approachability Guarantee

In a scalar zero-sum game, minimax converts a guarantee available when moving second into one available when moving first; in vector games, the corresponding guarantee is convergence of time averages.
For a response-satisfiable closed convex set and increments bounded at scale G, expected squared distance to the set is at most 4G²/t, giving distance on the order of 1/√t.

47:00 Projection onto the Target Set Defines a Normal

At each round, the learner projects the current average vector onto C and defines the normal vector as the average minus its closest point in C.
Convexity ensures this normal identifies a supporting hyperplane that separates the current average from the target set.

52:00 A Supporting Hyperplane Reduces the Vector Problem

The projection inequality shows that every point in C lies on the target side of the hyperplane normal to the projection residual.
Taking an inner product with that normal converts the next vector increment into a scalar objective, allowing a minimax theorem to be applied one round at a time.

58:00 Minimax Selects a Strategy on the Correct Side

The scalar game's payoff is the inner product of the current normal with the outcome increment minus the projection point.
Response satisfiability bounds the game value when the adversary moves first; finite-game minimax transfers the nonpositive bound to the actual order, with the learner moving first.

1:03:00 The Blackwell Projection-and-Minimax Algorithm

The learner maintains the running average, projects it onto the target set, and uses the projection residual to define the round's scalar game.
Solving that game for a minimax mixed strategy ensures the expected next increment is on the target side of the supporting hyperplane.

1:08:00 Running Averages Turn Local Progress into Convergence

The updated average is (1 − 1/t) times the previous average plus 1/t times the new vector increment.
Comparing the new average with the previous projection and expanding the squared norm produces a cross term whose conditional expectation is nonpositive under the minimax strategy.

1:17:00 Bounding Increments and Telescoping the Error

After translating the target set to contain zero, the projection inequality and Cauchy-Schwarz bound the difference between an increment and the previous projection by 2G.
Multiplying the squared-distance recurrence by t² makes it telescope, yielding expected squared distance at most 4G²/t.

1:22:00 Decision Calibration for Many Downstream Users

For decision calibration, learner actions are forecasts in an η-net and vector outcomes concatenate bias blocks for each action and outcome; copying the adversary's forecast would give zero expected bias, and the η-net approximates that response within η.
Roth gives a squared-distance bound of 8/t and calibration error on the order of √(8/t) + η; adding separate vector blocks extends the guarantee to many users with different utility functions and low swap regret for each.

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.