Frequency
Every 2 years; Remark: Next time: Spring 2024
Summary
This course provides an overview of recent developments in online learning, game theory, and variational inequalities and their point of intersection with a focus on algorithmic development. The primary approach is to lay out the different problem classes and their associated optimal rates.
Content
The dynamics of games have been studied by many different communities, such as online learning, optimization, and game theory. This course seeks to uncover the similarities and subtle differences of these perspectives towards a fundamental understanding of the underlying algorithms.
The course will broadly cover the following themes:
– Equilibrium concepts: source problems, solution concepts and their relationships.
– Online learning: the concept of regret, regret lower bounds, online learning algorithms, and online to batch conversion.
– Variational inequalities: monotone operators, algorithms, and their relationships to online learning
– Limited feedback in online learning: (semi-)bandit feedback, best of both worlds, stochastic approximation
– Extensions: linear bandits, combinatorial online learning, Markov decision processes, dynamics regret, adaptive regret
The course proceeds through a combination of books and recent papers and re-derive them under a common language.
Keywords
Online learning, bandits, game theory, variational inequalities, adaptivity, monotone operators, regret, lower-bounds
Learning Prerequisites
Recommended courses
EE-556 Mathematics of Data is recommended.
Important concepts to start the course
Basic probability and linear algebra.
Learning Outcomes
By the end of the course, the student must be able to:
• Choose
• Analyze algorithms
• Explain regret
• Produce a presentation
• Theorize appropriate structures in optimization
• Present concepts in game theory
Teaching methods
Lecture + active learning
Expected student activities
Build and present part of the material with the teaching team in form of a lecture.
Resources
Moodle Link
2023-2024 COURSE BOOKLET
Online learning in games Page 3 / 4
• https://go.epfl.ch/EE-735