Online Optimization and Learning in Games (Fall 2026)

Online Optimization and Learning in Games (Fall 2026)

Course Information

Overview

This course studies how a learner makes decisions in non-stationary or adversarial environments. We will discuss classic algorithms such as multiplicative weights and follow-the-perturbed-leader, and develop the general framework of online convex optimization. A central theme of the course is that a small set of no-regret principles can be used to understand a broad range of problems, including game theory, multi-objective learning, calibration, equilibrium computation, and learning in strategic environments.

Prerequisites

Probability, linear algebra, calculus, machine learning, convex analysis, mathematical maturity.

Grading

Late policy for assignments: Each late day results in 10% deduction in the grade of that assignment. The number of late days is calculated by rounding up (e.g., 1 hour late = 1 day late). Assignments cannot be submitted 3 days after the deadline.

Platforms

Schedule

One file of slides may be used for multiple lectures. Check Piazza for the recording passcode.

Date Topics Slides Recordings Assignments
8/26 Introduction Slides Recording  
8/31 Expert problem and online convex optimization: Follow the leader Slides Recording  
9/2 Exponential weights   Recording  
9/7 Follow the regularized leader   Recording HW1 (due on 9/27)
9/9 Follow the regularized leader   Recording  
9/14 Follow the perturbed leader   Recording  
9/16 Zero-sum game: The minimax theorem Slides Recording  
9/21 The minimax theorem   Recording  
9/23 Nash equilibrium   Recording  
9/28 Boosting   Recording  
9/30 Linear programming duality Slides Recording HW2 (due on 10/11)
10/5 Fall reading day (no class)      
10/7 Solving LP with no-regret algorithms   Recording  
10/12 Online learning with multiple objectives: Group-wise regret Slides Recording  
10/14 Interval regret   Recording  
10/19 Quiz 1      
10/21        
10/26        
10/28        
11/2        
11/4        
11/9 Learning with strategic players: Manipulating learning algorithms      
11/11        
11/16 Swap regret and robust learning      
11/18 Student presentation      
11/23 Student presentation      
11/25 Thanksgiving recess (no class)      
11/30 Student presentation      
12/2 Student presentation      
12/7 No class      

Resources