Incremental learning, game theory and applications

ECTS : 4

Volume horaire : 24

Description du contenu de l'enseignement :

This course focuses on the behavior of learning algorithms when several agents interacts : specifically, what happens when an agent that follows an online learning algorithm interacts with one or several agents doing the same?  The natural language to frame such questions is that of game theory. The course will begin with a short introduction to the topic : normal form games (in particular zero-sum, potential, and stable games), solution concepts (elimination of dominated strategies/rationalizability, Nash equilibrium, correlated and coarse correlated equilibrium, evolutionary stable strategies), and some extensions (Blackwell approachability). Subsequently, we will examine the long-term behavior of a variety of online learning algorithms (fictitious play, regret-matching, exponential weights, etc.). Time allowing, we will discuss links with evolutionary game dynamics, as well as applications to generative adversarial networks (GANs), traffic routing, prediction, or online auctions.

Compétence à acquérir :

• Basic of game theory: representation of strategic interactions, solution concepts, important classes of games.
• Long-run performance of learning procedures when several agents are playing against each other
• Familiarity with game dynamics

Mode de contrôle des connaissances :

To be discussed with students

Bibliographie, lectures recommandées :

1. Nicolò Cesa-Bianchi and Gábor Lugosi, Prediction, learning, and games, Cambridge University Press, 2006.
2. Drew Fudenberg and David K. Levine, The theory of learning in games, Economic learning and social evolution, vol. 2, MIT Press, Cambridge, MA, 1998.
3. Sergiu Hart and Andreu Mas-Colell, Simple adaptive strategies: from regret matching to uncoupled dynamics, World Scientific Series in Economic Theory - Volume 4, World Scientific Publishing, 2013. 
4. Vianney Perchet, Approachability, regret and calibration: implications and equivalences, Journal of Dynamics and Games 1 (2014), no. 2, 181–254. 
5. Shai Shalev-Shwartz, Online learning and online convex optimization, Foundations and Trends in Machine Learning 4 (2011), no. 2, 107–194.