CMPT 419/983 - Theoretical Foundations of Reinforcement Learning
Course overview
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
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
Lecture slides and readings
| Topic | Slides | References |
|---|---|---|
| Multi-armed Bandits, Explore-then-Commit | Lecture 1 | Chapters 4, 5, 6 of [LS20], [Refresher on Probability] |
| UCB, Linear Bandits, LinUCB | Lecture 2 | Chapters 7, 19 of [LS20], [Refresher on Linear Algebra] [List of inequalities] |
| LinUCB, Markov Decision Processes | Lecture 3 | Chapter 20 of [LS20], Chapter 2, 5.1 - 5.2 of [PC23] |
| Bellman Operators, Fundamental Theorem, Value Iteration | Lecture 4 | Chapter 5.2-5.5 of [PC23], [Lecture 2, Csaba notes] [Lecture 3, Csaba notes] |
| Policy Iteration, Linear Programming and MDPs | Lecture 5 | [Lecture 4, Csaba notes], Chapter 5.6, 5.8 of [PC23] |
| Monte-Carlo for Policy Evaluation, Temporal Difference Learning | Lecture 6 | Chapter 5,6 of [SB20] [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation] |
| Temporal Difference Learning, Approximate Policy Iteration | Lecture 7 | [Lecture 8, Csaba notes] |
| Approximate Policy Iteration, Politex, Mirror Descent | Lecture 8 | [Lecture 13, Csaba notes] [Lecture 14, Csaba notes] |
| Mirror Descent, Policy Gradient | Lecture 9 | Chapter 4 of [Convex Optimization: Algorithms and Complexity] |
| Softmax Policy Gradient, Natural Policy Gradient | Lecture 10 | [On the Global Convergence Rates of Softmax Policy Gradient Methods] [A Natural Policy Gradient] |
| Natural Policy Gradient, Handling stochasticity | Lecture 11 | [Understanding the Effect of Stochasticity in Policy Optimization] |
| TRPO/PPO, Exploration in Tabular MDPs | Lecture 12 | [Trust Region Policy Optimization], Chapter 7 of [AJKS22] |