Algorithms for learning in simple and complex games
- Garant předmětu:
- 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:
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)
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: