This chapter introduces no-regret learning, and introduces several of the most popular algorithms, including online mirror descent and the multiplicative weights update algorithm. We also prove von Neumann’s minimax theorem via no-regret learning.

This chapter introduces no-regret learning with predictions, and introduces optimistic online mirror descent. Then, we show that self-play in two-player zero-sum games with optimistic and stable online learning algorithms leads to a 1/T rate of convergence to equilibrium.

This chapter studies games with vector-valued payoffs, and introduces Blackwell approachability, along with a proof of Blackwell’s approachability theorem. Then, we show how this leads to the regret matching algorithm, as well as the regret matching+ algorithm. The latter is a key component of superhuman poker AIs.

This chapter introduces the idea of computing a two-player zero-sum Nash equilibrium via “self play,” where two no-regret learning algorithms play against each other. We prove that the uniform average of the iterates converges to a Nash equilibrium. Then, we introduce several practical tricks for speeding up self-play, including linear iterate averaging and alternation.