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 Swap regret   Recording  
10/26 General-sum game Slides Recording  
10/28 Equilibrium   Recording  
11/2 CE, CCE   Recording  
11/4       HW3 (due on 11/12)
11/9 Algorithmic collusion      
11/11        
11/16        
11/18 Quiz 2      
11/23 Student presentation (remote): Differential privacy, online conformal prediction      
11/25 Thanksgiving recess (no class)      
11/30 Student presentation (remote): Human-AI collaboration      
12/2 Student presentation (remote): Multi-distribution learning, omniprediction      
12/7 Student presentation (remote): Incentive design, counterfactual regret minimization      

Resources