CMPT 419/983 - Theoretical Foundations of Reinforcement Learning (Fall 2023)

Instructor: Sharan Vaswani

TA: Michael Lu

Course Objective: Numerous applications in machine learning involve interacting with the world, collecting data, and reasoning about it, all with incomplete information. Reinforcement Learning (RL) is a general framework for interactive learning and has been used for applications in clinical trials, monitoring industrial plants, robotics, games such as Atari and Go, and computational marketing. This course introduces the foundational concepts in bandits and RL from a rigorous theoretical perspective. The course intends to give students experience in: (1) Proving theoretical guarantees for reinforcement learning algorithms (2) Mapping problems in practical applications (e.g. recommender systems, social networks) to the RL framework (3) Developing and analyzing new bandit and RL algorithms

Prerequisites: Probability, Linear Algebra, Multivariable Calculus, Undergraduate Machine Learning

Textbook: There is no required textbook. We will use the following resources:

• Reinforcement Learning: An Introduction. Sutton and Barto, 2020 [SB20]
• Bandit Algorithms. Lattimore and Szepesvari, 2020 [LS20]
• Introduction to Markov Decision Processes. Puterman, Chan, 2023 [PC23]
• Reinforcement Learning: Theory and Algorithms. Agarwal, Jiang, Kakade and Sun, 2022 [AJKS22]

Piazza for course-related questions and discussions.

List of topics

• Basics: Concentration inequalities, (Online) Convex Optimization
• Bandits: Multi-armed/Contextual bandits framework, Regret minimization, Epsilon-greedy, Upper-confidence Bound
• Markov Decision Processes: Structural properties, Bellman equation, Linear programming view of MDPs
• MDPs: Algorithms in the tabular setting: Policy Evaluation, Temporal Difference Learning, Value Iteration, Policy Iteration
• MDPs: Algorithms with function approximation: Approximate policy iteration, Politex, Policy gradients
• MDPS: Regret minimization in the online setting using UCB-VI

Schedule

• UAlberta
• UToronto
• Harvard
• Cornell
• UIUC
• UMichigan