Algorithms for learning in simple and complex games

The course is not on the list Without time-table
Code Completion Credits Range Language
01ALUC Z 1 1 Czech
Department of Mathematics

The goal of this series of lectures is to get form the very basics of game theory and machine learning all the way to solid understanding of the algorithm used in DeepStack. We will explain how games can be formally modeled, what are meaningful definitions of optimal strategies in games and what is Nash equilibrium in particular. Afterwards, we will focus on simple learning mechanisms in repeated decision-making problems called multi-armed bandit problems. We will show basic properties of learning in these models and then investigate what happens if these algorithms are run against each other in a game. This will form the bases of an algorithm for computing Nash equilibria in simple zero-sum games, which can be extended to Counterfactual Regret Minimization (CFR) in extensive form games. Next, we will explain why it is complicated to decompose extensive form game to independent parts and how CFR-D can solve this problem under certain conditions. Finally, we will briefly introduce deep neural networks and combine all the introduced components to the first algorithm that was able to beat professional poker players.

Syllabus of lectures:
Syllabus of tutorials:
Study Objective:

Acquired knowledge: Students will learn the basic concepts of game theory. They will acquire the theoretical foundation for understanding the state-of-art algorithms for solving the games with incomplete information, like card games.

Acquired skills: Modeling problems from game theory and proposing algorithms of artificial intelligence for their solution.

Study materials:

Compulsory literature:

M. Moravčík, M. Schmid, N. Burch, V. Lisý, D. Morrill, N. Bard, T. Davis, K. Waugh, M. Johanson, M. Bowling, DeepStack: Expert-level artificial intelligence in heads-up no-limit poker, Science, Vol. 356, Issue 6337, pp. 508-513 (2017)

Optional literature:

J. Nash, Equilibrium points in n-person games, Proceedings of the national academy of sciences 36.1, pp. 48-49 (1950)

N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani: Algorithmic Game Theory, Cambridge University Press, 2007

Further information:
No time-table has been prepared for this course
The course is a part of the following study plans:
Data valid to 2020-07-04
For updated information see http://bilakniha.cvut.cz/en/predmet5635306.html