Course material & Lecture notes
■ Nonlinear Optimization (MIT 6.7220 / 15.084; Spring 2025, 2024)
Introduction to the fundamentals of nonlinear optimization theory and algorithms.
When applicable, emphasis is put on modern applications, especially within machine learning and its sub-branches,
including online learning, computational decision-making, and nonconvex applications in deep
learning.
Course materials (Spring 2025)
Course Homepage (Spring 2025) Course materials (Spring 2024)
|
 Course page |
■ Topics in Multiagent Learning (MIT 6.S890; Fall 2024, 2023)
This new graduate course, co-developed with Costis Daskalakis, presents the foundations of multi-agent systems from a combined game-theoretic, optimization and
learning-theoretic perspective, building from matrix games (such as rock-paper-scissors) to stochastic games, imperfect
information games, and games with non-concave utilities. We present manifestations of these models in machine learning
applications, from solving Go to multi-agent reinforcement learning, adversarial learning and broader multi-agent deep
learning applications. We discuss aspects of equilibrium computation and learning as well as the computational complexity
of equilibria. We also discuss how the different models and methods have allowed several recent breakthroughs in AI,
including human- and superhuman-level agents for established games such as Go, Poker, Diplomacy, and Stratego.
Course materials (Fall 2024)
Course Homepage (Fall 2024) Course materials (Fall 2023)
Course Homepage (Fall 2023) |
 Course page |
■ Computational Game Solving (CMU 15-888; Fall 2021)
This new graduate course, co-developed with Tuomas Sandholm at CMU, focuses on multi-step imperfect-information games. Imperfect-information games are significantly more complex than perfect-information games like chess and Go, and see emergence of signaling and deception at equilibrium. There has been tremendous progress in the AI community on solving such games since around 2003. The course covers the fundamentals and the state of the art of solving such games.Course materials (Fall 2021)
|
2021-09-09
html | pdf |
[L02]
Representation of strategies in tree-form decision spaces
Behavioral and sequence-form representation of a strategy. Computation of expected utilities given the sequence-form representation (multilinearity of expected utilities). Kuhn's theorem: relationship between normal-form and sequence-form strategies. Bottom-up decomposition of the sequence-form polytope.
|
|
2021-09-14
html | pdf |
[L03]
Hindsight rationality and regret minimization
Phi-regret minimization. Special cases: external regret minimization, internal regret minimization, swap regret. Solution to convex-concave saddle-point problems via regret minimization. Applications to bilinear saddle-point problems such as Nash equilibrium, optimal correlation, etc.
|
|
2021-09-16
html | pdf |
[L04]
Blackwell approachability and regret minimization on simplex domains
Blackwell game approach and construction of regret matching (RM), RM+.
|
|
2021-09-21
html | pdf |
[L05]
Regret circuits and the Counterfactual Regret Minimization (CFR) paradigm
Treeplex case: regret circuits for Cartesian products and for convex hull. Construction of CFR and pseudocode; proof of correctness and convergence speed.
|
|
2021-09-28
html | pdf |
[L07]
Optimistic/predictive regret minimization via online optimization
Online projected gradient descent. Distance-generating functions. Predictive follow-the-regularized-leader (FTRL), predictive online mirror descent (OMD), and RVU bounds. Notable instantiations, e.g., optimistic hedge / multiplicative weights update. Accelerated convergence to bilinear saddle points. Dilatable global entropy.
|
|
2021-09-30
html | pdf |
[L08]
Predictive Blackwell approachability
Blackwell approachability on conic domains. Using regret minimization to solve a Blackwell approachability game. Abernethy et al.’s construction. Predictive Blackwell approachability.
|
|
2021-10-05
html | pdf |
[L09]
Predictive regret matching and predictive regret matching plus
Connections between follow-the-regularized-leader / online mirror descent and regret matching / regret matching plus. Construction of predictive regret matching and predictive regret matching plus.
|
|
2021-10-07
html | pdf |
[L10]
Monte-Carlo CFR and offline optimization techniques
Regret minimization with unbiased estimators of the utilities. Game-theoretic utility estimators (external sampling, outcome sampling). Offline optimization methods for two-player zero-sum games. Accelerated first-order saddle-point solvers (excessive gap technique, mirror prox). Linear programming formulation of Nash equilibrium strategies. Payoff matrix sparsification technique.
|
|
2021-11-11
html | pdf |
[L19]
Sequential irrationality and Nash equilibrium refinements
Sequential irrationality. Trembling-hand equilibrium refinements: quasi-perfect equilibrium (QPE) and extensive-form perfect equilibrium (EFPE). Relationships among refinements. Computational complexity. Trembling-hand linear program formulation of QPE and EFPE. Scalable exact algorithms for QPE, and EFPE.
|
|
2021-11-16
html | pdf |
[L20]
Correlated strategies and team coordination
Team maxmin equilibrium and TMECor; why the latter is often significantly better. Realization polytope: low dimensional but only the vertices are known and not the constraints.
|
Course Homepage (Fall 2021)
Handouts
|
2024-04-19
html | pdf |
Near-optimal learning in imperfect-information sequential games (and other combinatorial convex settings)
MIT Theory Reading Group (3h whiteboard talk)
|
Reports of typos are always welcome! Please reach out at gfarina AT mit.edu.