Course Description

Schedule

Part I: Online Learning (John)

• Lecture 01 -- 2025.09.16
  Introduction to Online Learning
  

  Prediction with expert advice; online convex optimization; external regret; Online Gradient Descent algorithm and regret bound.

  [notes pdf]
• Lecture 02 -- 2025.09.18
  Follow-the-Regularized-Leader: No-Regret via Regularization
  

  Family of leader-based algorithms, analysis of Follow-the-Regularized-Leader (FTRL) via coupling with Be-the-Leader/Follow-the-Leader, Multiplicative Weights Update as FTRL, lower bounds for online learning.

• Lecture 03 -- 2025.09.23
  Follow-the-Perturbed-Leader and Online Mirror Descent: No-Regret via Perturbation and Penalty.
  

  Follow-the Perturbed-Leader (FTPL) analysis, equivalence between FTPL and FTRL, Online Mirror Descent (OMD) analysis.

• Lecture 04 -- 2025.09.25
  Online Learning with Bandit Feedback
  

  Bandit feedback model, expected regret and pseudo-regret, EXP3 algorithm for adversarial bandits, Explore-the-Commit and UCB algorithms for stochastic bandits.

• Lecture 05 -- 2025.09.30
  Phi-Regret Minimization
  

  Beyond external regret: swap-regret, internal-regret, and the Phi-Regret framework. Blum-Mansour and Stoltz-Lugosi algorithms.

• Lecture 06 -- 2025.10.02
  Blackwell Approachability and Regret Matching
  

  Blackwell's Approachability theorem, Regret Matching (RM) and Regret Matching+ (RM+) algorithms.

Part II: Learning in Normal-Form and Stochastic Games (Anas)

• Lecture 07 -- 2025.10.07
  Introduction to Normal-Form Games and Nash Equilibria
  

  Normal-Form Games, Nash equilibria (NE), game classes (potential, zero-sum, decomposition).

• Lecture 08 -- 2025.10.09
  No-Regret Learning in Games and Learning Nash Equilibria in Zero-Sum and Potential Games
  

  Hindsight rationality, proof of minimax theorem via online learning, learning NEs in potential games.

• Lecture 09 -- 2025.10.14
  Learning (Coarse)-Correlated Equilibria in General-Sum Games
  

  (Coarse)-correlated equilibria, time-average convergence via no-phi-regret learning, average vs. last-iterate convergence.

• Lecture 10 -- 2025.10.16
  Optimistic Learning and Social Welfare of No-Regret Dynamics
  

  Optimistic FTRL algorithms, RVU bounds, individual vs. sum of regrets, fast convergence of social welfare.

• Lecture 11 -- 2025.10.21
  Introduction to Stochastic Games and Multi-Agent Reinforcement Learning
  

  Introduction to Markov Decision Processes (MDPs) and Reinforcement Learning, definition of stochastic games, Shapley's minimax theorem, existence of Nash equilibria.

• Lecture 12 -- 2025.10.23
  Learning Nash Equilibria in Stochastic Games
  

  Independent and decentralized learning, zero-sum Markov games and Markov potential games, policy gradient methods.

Part III: Learning in Extensive-Form and Continuous Games (Joseph)

• Lecture 13 -- 2025.11.06
  Introduction to Extensive-Form Games
  

  Game trees, imperfect information, perfect recall, strategy representations, Kuhn's theorem.

• Lecture 14 -- 2025.11.11
  Learning Equilibria in Extensive-Form Games
  

  Counterfactual Regret Minimization algorithm (CFR) and speedups.

• Lecture 15 -- 2025.11.13
  Introduction to Continuous Games
  

  Concave games, Rosen's theorem, variational inequalities, monotone games, zero-sum games and Gradient Descent Ascent (GDA), divergence of GDA in bilinear case.

• Lecture 16 -- 2025.11.18
  Learning Equilibria in Continuous Games
  

  Proximal point method, Optimistic GDA and Extragradient algorithms for zero-sum games, learning equilibria in potential games, general concave games.

• Lecture 17 -- 2025.11.20
  Price of Anarchy and Equilibrium Selection
  

  Braess' paradox, Pigou's network, smooth games, introduction to Price of Anarchy (PoA) bounds.

Part IV: Special Topics

• To be announced...

Assignments and Project

Resources