6.S890: Topics in Multiagent Learning
We learned about multiagent learning, mostly in the context of game theory. I optimized a pretty good solver for the final project - it was pretty cool!
From the course website for Fall 2024: While machine learning techniques have had significant success in single-agent settings, an increasingly large body of literature has been studying settings involving several learning agents with different objectives. In these settings, standard training methods, such as gradient descent, are less successful and the simultaneous learning of the agents commonly leads to nonstationary and even chaotic system dynamics.
Motivated by these challenges, this course presents the foundations of multi-agent systems from a combined game-theoretic, optimization and learning-theoretic perspective. We start with basic matrix games, such as rock-paper-scissors, and advance to more complex forms including imperfect information games and structured games like combinatorial games, polymatrix games, and stochastic games. Topics will cover various equilibrium concepts, aspects of equilibrium computation and learning, as well as the computational complexity of finding equilibria. Additionally, we will examine how these models and methods have driven recent breakthroughs in AI, producing human- and superhuman-level agents for well-known games such as Go, Poker, Diplomacy, and Stratego.
Table of Contents
- Lecture 1: Game Types
- Lecture 2: Normal Form Games, Nash Equilibrium & Existence Proof
- Lecture 3: Sperner → Brouwer → Nash’s Theorem
- Lecture 4: Nash Equilibria, Two-player Zero-Sum & Max–Min Strategies, Two-player General-Sum & LCP, Coarse Correlated Equilibrium
- Lecture 5: Coarse Correlated Equilibrium, Existence of CCE
- Lecture 6: Support Enumeration Algorithms, Scarf’s Algorithm, The Lemke–Howson Algorithm
-
Pset 1: Normal Form Games, Linear Complementary Problems, Sperner’s Lemma, Coarse Correlated Equilibrium
- Lecture 7: Learning in Games, Φ-Regret Minimizer
- Lecture 8: Φ-Regret and Nash Equilibria, Building a Learner
- Lecture 9: Regret Matching (RM & RM+), Multiplicative Weights Update (MWU), Online Projected Gradient Ascent (OGD), Online Mirror Descent (OMD)
- Lecture 10: Extensive-Form Games, Strategies in Extensive-Form Games
- Lecture 11: Sequence-Form Strategies, Counterfactual Regret Minimization (CFR) for Extensive-Form Games (EFGs)
- Lecture 12: Project Brainstorming
- Lecture 13: Counterfactual Regret (CFR) Example, Equilibrium Perfection, Quasi-Perfect Equilibrium
-
Pset 2: Optimal Regret Bounds, Finding Coarse Correlated Equilibria, Dominated Strategies and Correlated Equilibria, Game Representations, EFG Solver
- Lecture 14: Stochastic Games, Equilibrium Existence
- Lecture 15: Stochastic Games & Equilibrium Existence II
-
Pset 3: Counterfactual Regret Minimization, Stochastic Games and EFGs
- Lecture 20: Deep RL for Imperfect Information Games, Belief-Based Representation (Markov)
- Lecture 21: Decision Making Under Massive Hidden Information
- Lecture 22: Hardness of Nash
- Team Belief DAG: Paper Notes
- Project: Team Leduc Poker Challenge Writeup