Module COMP3821: Reinforcement learning & Algorithmic Game Theory

Department: Computer Science

COMP3821: Reinforcement learning & Algorithmic Game Theory

Prerequisites

• COMP2181 Theory of Computation

Corequisites

• COMP3NEW5 Deep Learning & Computer Vision

Excluded Combination of Modules

• None

Aims

• To explore how strategic decision-making and learning from interaction can be used by software agents.
• To learn how to design agents with intelligent behaviour, taking actions to control the environment and maximise rewards.
• To understand the notion of a game, relevant concepts, and other basic notions and tools of game theory, as well as the main applications where such concepts are used and applied.
• To understand computational models of learning in dynamic environments.
• To understand how agents can learn to act optimally in multi-agent environments, where other agents form part of the environment.

Content

• The module covers Algorithmic Game Theory (AGT) and Reinforcement Learning (RL). Each submodule is run over one term.
• Introduction to AGT: what is a game? Strategy, preferences, payoffs.
• Bimatrix games: strategies and payoffs; Nash equilibria.
• Extensive games with Perfect Information.
• Mathematical and algorithmic foundations of market equilibria.
• Routing Games on Networks; Congestion Games.
• Mechanism design and Combinatorial Auctions.
• Introduction to RL
• Markov decision processes and planning by dynamic programming.
• Model free prediction and control.
• Value-based and policy-based reinforcement learning.
• Scaling up reinforcement learning approaches with deep learning.
• Integrating learning and planning, and balancing exploration/exploitation.

Learning Outcomes

• On completion of the module, students will be able to demonstrate:
• An understanding of key game theoretic notions and ideas, and their connections to computer science and economics.
• An understanding of the impact of game theory and mechanism design on contemporary applications.
• An understanding of the key features of reinforcement learning and differences with non-interactive learning.
• An understanding of state-of-the-art reinforcement learning algorithms.
• An understanding of the issues faced in scaling reinforcement learning approaches using deep learning.

• On completion of the module, students will be able to demonstrate:
• The ability to apply techniques and methods from algorithmic game theory to tackle fundamental game theoretic problems.
• The ability to identify key strategic aspects of real-world scenarios and model those scenarios as strategic games.
• An ability to use modern libraries to design, train, validate and test deep reinforcement learning models.
• An ability to find RL based solutions with respect to the task or environment.
• An ability to design bespoke RL algorithms based on the problem and the environment, such as whether in continuous or discrete action spaces.
• An ability to solve complex learning and planning problems in dynamic environments.

• On completion of the module, students will be able to demonstrate:
• A scientific approach to the design and testing of algorithmic techniques in a broad range of applications
• An ability to think critically
• An ability to work with abstract problems
• An ability to undertake general problem solving
• A scientific approach to the designing, training, validation, and testing of reinforcement techniques in a broad range of applications.
• An ability to design new environments and tailored agents that learn to control the environments.
• An ability to design and implement state-of-the-art deep reinforcement learning approaches.

Modes of Teaching, Learning and Assessment and how these contribute to the learning outcomes of the module

• Lectures provide the material required to be learned and the application of the theory to practical examples.
• AGT: Formative exercises are given to the students to assess their understanding of the taught material.
• RL: Computer classes enable students to acquire necessary coding skills, develop a practical understanding of the underpinning theory, learn how to effectively use relevant libraries, and receive feedback on their work.
• AGT: The summative assessments test the knowledge acquired and the students' ability to use this knowledge to solve game theoretic problems.
• RL: The practical assessments consist of tasks set during selected practicals to evidence students’ ability to train and evaluate deep reinforcement learning architectures and algorithms.

Teaching Methods and Learning Hours

Summative Assessment

Formative Assessment:

Example formative exercises are given during the course. Formative feedback will be provided to the students during the computer classes.

■ Students who do not attend monitored activities shown under Teaching Methods and Learning Hours, or who fail to complete the summative or formative assessment(s) specified above, may be subject to the Academic Progress procedures defined in the University's General Regulation V, and may be required to leave the University.