Games in Machine Learning
PhD course, spring 2024/2025
Politecnico di Milano

Multi-Player Learning in Modern Machine Learning

Many contemporary machine learning systems involve multiple interacting agents, each optimizing distinct—often conflicting—objectives. These scenarios arise in settings such as Stackelberg games, generative adversarial networks (GANs), multi-agent reinforcement learning (MARL), collaborative robotics, and competitive drone systems. Even standard single-model training can exhibit game-theoretic structures, including adversarial robustness, learning under distributional shift, and causal inference.

This course introduces students to the theory and practice of learning in multi-player systems, with a strong focus on gradient-based methods and convergence to equilibrium solutions. We will explore:

• Foundations: Core principles from convex optimization and zero-sum min-max games.
• Unifying Framework: Variational Inequalities (VIs) as a general analytical tool for multi-player learning.
• Applications: Practical challenges in multi-agent RL, GAN training dynamics, and beyond.

Key Takeaways

• Understand iterative learning dynamics in single- and multi-agent environments.
• Identify and address challenges in min-max and non-convex optimization.
• Apply a unified VI-based framework to analyze n-player learning systems.
• Gain practical skills for designing ML systems in multi-agent settings.

By the end of the course, students will be well-equipped to design, analyze, and implement learning algorithms for complex, interactive ML systems—bridging foundational theory with cutting-edge applications.

Lecturer:

• Tatjana Chavdarova is visiting professor at Politecnico di Milano, with a research focus on the intersection of game theory and machine learning.

Course Materials

• Lecture 1: Introduction

  • Slides • Annotated
  Covers:
  • Games & Inteligence: Historical Remarks
  • Optimization Intro
  • Game Theory Intro
  • What Makes a Game? (an ML perspective)
  • Motivation to Study Games in ML
  

• Lecture 2: Optimization

  • Slides-Part-1 • Annotated-Part-1 • Slides-Part-2 • Annotated-Part-2 • Exercises • Solutions
  Covers:
  • Optimization Intro
  • Smooth Functions & Gradient Descent
  • Convexity: Sets & Functions
  • Gradient Descent Convergence on (Strongly) Convex Functions
  • Stochastic Gradient Descent
  

• Lecture 3: Two Player Games

  • Slides • Annotated • Exercises • Solutions
  Covers:
  • Two-player Games: Normal-Form, Nash, Zero-sum, General-sum
  • Minimax Theorem & Strong Linear Programming Duality Connection
  • Methods: Gradient Descent, Extragradient, Proximal Point, Optimistic Gradient Descent, Lookahead
  • Minimax Theorem Proof Through Connection to Strong Linear Programming Duality
  • PP perspective of ExtraGradient & Optimistic Gradient Descent
  

• Lecture 4: Variational Inequality

  • Slides • Annotated • Exercises • Solutions
  Covers:
  • Variational Inequality: Framework & Examples
  • Classes: Lipschitz, Contractive, Averaged, Non-expansive, (strongly) Monotone, Cocoercive, Cyclic
  • Spectral Viewpoint of VI Classes
  • Monotone Inclusion
  • Fixed Point Iteration
  • Convergence of Averaged Operators
  • Local Convergence
  

• Lecture 5: Operator Theory & Operator Theory

  • Slides • Annotated • Exercises • Solutions
  Covers:
  • Crash course: Maximality, (Reflected) Resolvent
  • Operator Splitting: forward↔backward, Douglas–Rachford Splitting etc.
  

• Lecture 6: Mirror Methods for Games & Mirror Prox

  • Slides • Annotated • Exercises • Solutions
  Covers:
  • Motivation
  • Variable-Metric Methods
  • Mirror Descent: Mirror maps, Bregman divergence, Algorithm
  • Mirror Prox
  

• Lecture 7: Advanced Topics: Constrained Games & Analysis in Continious-time

  • Slides • Annotated • Exercises • Solutions
  Covers:
  • Part I - Solving Constrained Games: VI KKT & ACVI
  • Part II - Continuous-Time Analysis: HRDEs, Routh-Hurwitz stability, Lyapunov stability
  

• Lecture 8: Practical Aspects of Game Optimization

  • Slides • Annotated • Code-demo
  Covers:
  • Part I: Generative Adversarial Networks: Framework's Equilibrium & Training
  • Part II: Game Optimization Impact in Reinforcement Learning
  

Resources & Main References

Contact

For typos, remarks, or you'd like to use the latex code of the slides feel free to reach out at: tatjana.chavdarova[at]polimi[dot]it.