Understanding Learning in Games Seminar
Explore the intersection of Game Theory and Machine Learning in the context of Learning in Games. Discover how decision-makers adapt strategies to maximize their utility, with emphasis on Multi-Agent Learning. Topics include AI for Board Games, Equilibrium Computation in Auctions, and various solution concepts such as Nash equilibria and Correlated equilibria. Delve into different types of games, learning environments, and solution concepts in strategic and adversarial scenarios.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Learning in Games Seminar Introductory Meeting and Q&A 6th February, 2024 Chair of Decision Sciences & Systems
Course Content Game Theory: strategic interactions of multiple decision-makers This seminar: will explore the subfield of Learning in Games, where these decision-makers are agents that learn to adapt their strategies in order to maximize their own expected utility The topics are located at the intersection of Game Theory and Machine Learning, particularly Multi-Agent Learning In recent years, there has been renewed interest as well as big breakthroughs in this field, fueled by more powerful computation and deep learning increasing deployment of autonomous systems (bots) in the economy Chair of Decision Sciences & Systems 2
Course Content Topics explored in this seminar may include Applications E.g.: AI for Board Games; economical applications such as Equilibrium Computation in Auctions Algorithms E.g.: Counterfactual Regret Minimization, AlphaZero Theory E.g.: Equilibria and Game Dynamics, Complexity, Evaluation of Agent Strength Chair of Decision Sciences & Systems 3
Course Content Learnability What concepts can be learned in presence of strategic and adversarial behavior? How to design learning in such scenarios? Types of games Normal-form game or extensive-form game Zero-Sum games or general-sum games Two-player games Learning environments Offline (Stochastic) Learning Online (Adversarial) Learning Different solution concepts Nash equilibria Correlated equilibria Chair of Decision Sciences & Systems 4
Introductory Example: Matrix Game Let (?,?) be an ? ? bimatrix game, i.e., a finite two-player game player 1, the row player, has pure strategies ? ? = {1, ,?} player 2, the column player, has pure strategies ? ? = {1, ,?} ? and ? are the payoff matrices for players 1 and 2 If player 1 chooses ? and player 2 chooses ?, the payoffs to players 1 and 2 are ??? and ???, respectively. Prisoner's dilemma: B B B silent betrays A -1 0 A silent -1 -3 -3 -2 A betrays 0 -2 Chair of Decision Sciences & Systems 5
Introductory Example: Fictitious Play The classical learning process known introduced by Brown (1951) Two players playing a finite game with repeatedly After arbitrary initial moves, in every round each player plays a pure best response against the empirical strategy distribution of the opponent In zero-sum games, the empirical strategy distributions always converge to the set of Nash equilibria; however, this does not hold for other types of games For the ? ? bimatrix game (?,?), the action sequence ??,?? ? is a fictitious play process if?1 {1, ,?}and ?1 1, ,? and for all ? > 1 ?? BR1? ? and ?? BR2? ? where the beliefs are given by ? ? =1 ? ?=1 ??and? ? =1 ? ? ? ?=1 ?? Chair of Decision Sciences & Systems 6
General Literature Recommendations Fudenberg, et al. (1998): The theory of learning in games Foundation for equilibrium theory, replicator dynamics and fictious play, normal and extensive form games Can be borrowed at chair, TUM library has a few hard-copies Young (2004): Strategic learning and its limits Regret and no-regret learning, equilibrium concepts, fictious play Can be borrowed at chair Shalev-Shwartz (2011): Online learning and online convex optimization Survey paper on online learning that introduces , among other, FTL and FTRL, Available online Nisan, Roughgarden, Tardos, Vazirani (2007): Algorithmic Game Theory Collection of guest chapters on different topics in AGT, e.g., complexity, learning, applications, Sutton & Barto (2018): Reinforcement Learning. An Introduction (2nd edition) The standard reference for (single-agent) reinforcement learning. Latest edition available for free at http://www.incompleteideas.net/book/the-book.html Chair of Decision Sciences & Systems 7
Format Each student will be assigned an individual topic and prepare a presentation as well as a short summary paper Quiz Presentation 45 min presentation of topic Handout Mini-quiz for the audience: < 1 min with MC or single-word responses Short handout (extended abstract) of maximal 2 pages We will have biweekly meetings throughout the semester with two topics being presented in each meeting Attendance of all meetings is mandatory interaction with the other students' work is expected: E.g., answering prepared mini-quizzes Chair of Decision Sciences & Systems 8
Impression: Last Years Topics 01 02 03 04 05 06 07 08 09 10 11 12 13 14 Normal Form Games & Equilibria Regret Matching & Convergence Zero-Sum, Fictitious Play, MiniMax MDP + Q-Learning Policy Gradients Stochastic Games + Solution Concepts + Shapley Algorithm Lemke-Howson Algorithm Multiplicative Weights & Replicator Dynamics Regret Policy Gradients Collusion Policy Space Response Oracles Sophisticated / Bayesian Learning Inverse Reinforcement Learning Neural Equilibrum Solvers Chair of Decision Sciences & Systems 9
Registration All students must apply for the seminar via email and the matching system Further information (including the application procedure) can be found on the course homepage Chair of Decision Sciences & Systems 10
Q&A Contact mete.ahunbay@cit.tum.de Chair of Decision Sciences & Systems 11
