CS 6789: Foundations of Reinforcement Learning

Modern Artificial Intelligent (AI) systems often need the ability to make sequential decisions in an unknown, uncertain, possibly hostile environment, by actively interacting with the environment to collect relevant data. Reinforcement Learning (RL) is a general framework that can capture the interactive learning setting and has been used to design intelligent agents that achieve super-human level performances on challenging tasks such as Go, computer games, and robotics manipulation.

This graduate level course focuses on theoretical and algorithmic foundations of Reinforcement Learning. The four main themes of the course are (1) fundamentals (MDPs, computation, statistics, generalization) (2) provably efficient exploration (and high dimensional RL) (3) direct policy optimization (e.g. policy gradient methods), (4) further topics (control, offline RL, and imitation learning).

After taking this course, students will be able to understand both classic and state-of-art provably correct RL algorithms and their analysis. Students will be able to conduct research on RL related topics.


Instructors: Wen Sun (Cornell) and Sham Kakade (University of Washington & Microsoft Research)

TAs: Princewill Okoroafor

Lecture time: Tuesday/Thursday 11:25am-12:40 ET

Office hours: By Appointment

Location: Gates Hall G114

Contact: cornellcs6789@gmail.com.

Please communicate to the instructors and TA only through this account. Emails not sent to this list, with regards to the course, will not be responded to in a timely manner.

Zoom Information

Zoom information has been posted on Ed Discussion. Students enrolled in the Ithaca section are required to show up in person. Students enrolled in the Cornell Tech section can join via zoom.

If you are not enrolled/wait listed (or you are not from Cornell), but want to have access, please email cornellcs6789@gmail.com to ask for permission. We will make a decision based on the capacity of the class and your research background (please in email briefly describe your research interestes and your background on machine learning theory. Thanks).


This is an advanced and theory-heavy course: there is no programming assignment and students are required to work on a theory-focused course project.

Students need strong grasp on Machine Learning (e.g., CS 4780), Probability and Statistics (e.g., BTRY 3080 or ECON 3130, or MATH 4710), Optimization (e.g., ORIE 3300), and Linear Algebra (e.g., MATH 2940). For undergraduate students enrollment: permission of instructor with minimum grade A in CS 4780.

Grading Policies

Assignments 55% (HW0:10%, HW1-HW3: 15% each), Project 40%, Reading 5%, Participation bonus 5%

All homework will be mathematical in nature, focussing on the theory of RL and bandits; there will not be a programming component. The entire HW must be submitted in one single typed pdf document (not handwritten). HW0 is MANDATORY to pass to satisfactory level; it is to check your knowledge of the prerequisites in probability, statistics, and linear algebra.

Homework Rules: Homework must be done individually: each student must understand, write, and hand in their own answers. It is acceptable for students to discuss problems with each other; it is not acceptable for students to share answers and look at another students written answers. You must also indicate on each homework with whom you collaborated with and what online resources you used.

Late days: Homeworks must be submitted by the posted due date. You are allowed up to 6 total LATE DAYs for the homeworks throughout the entire semester. These will be automatically deducted if your assignment is late. For example, any day in which an assignment is late by up to 24 hours, then one late day will be used. After your late days are used up, late penalties will be applied: any assignment turned in late will incur a reduction in score by 33% for each late day, so if an assignment is up to 24 hours late, it incurs a penalty of 33%. Else if it is up to 48 hours late, it incurs a penalty of 66%. And any longer, it will receive no credit. We will track all your late days and any deductions will be applied in computing the final grades. If you are unable to turn in HWs on time, aside from permitted days, then do not enroll in the course.

Participation/extra effort bonus: We encourage participation including asking/answering questions in lectures and ED discussion, and extra effort on reading the book chapters (e.g., proof reading additional chapters and sending back comments/feedback).

Reading Assignment

Please sign up for reading materials here.

Reading assignment is done in group (size 2 or 3). Each group will read the assigned chapter in the AJKS book (V3). You are required to submit a one page report that summarizes the chapter. In addition to this, the requirement is that you also carefully read the chapter, checking for errors, typos, and arguments/explanations that are not clear; please point this out to the instructors either in a separate page in the report or via Ed Discussion. The expectation is that you check all mathematical steps in the chapter; this gives you an opportunity to obtain a mastery of the chapter that you choose.

Course Project

Please see the course project page. It is a course requirement that you be in attendance for all student presentations. In addition, we ask everyone to block approximately 2 hours for each of the presentation sessions (tentatively there will be 3 presentation sessions at the end of the semester)

Diversity in STEM

While many academic disciplines have historically been dominated by one cross section of society, the study of and participation in STEM disciplines is a joy that the instructors hope that everyone can pursue, regardless of their socio-economic background, race, gender, etc. The instructors encourage students to both be mindful of these issues, and, in good faith, try to take steps to fix them. You are the next generation here.

Course Notes: RL Theory and Algorithms

The course will be largely based of the working draft of the book "Reinforcement Learning Theory and Algorithms", available here. We will be updating these notes in AJKS throughout the course of the term. If you find typos or errors, please let us know. We would appreciate it!

Honor Code

Cornell University Code of Academic Integrity, CS Department Code of Academic Integrity.

Schedule (tentative)

Lecture Reading Slides/HW
08/26/21 Fundamentals: Markov Decision Processes Ch.1 Slides, Annotated slides, HW0
08/31/21 Fundamentals: Policy Iteration and Value Iteration Ch.1 Slides, Annotated slides
09/02/21 Fundamentals: Computational Complexity & The LP-Formulation Ch.1 Slides, Annotated slides
09/07/21 Fundamentals: Statistical Limits with a Generative Model Ch.2 Slides, Annotated slides,
09/09/21 Fundamentals: Generalization in RL Ch.5 Slides_1, Slides_2, Annotated Slides_1, Annotated Slides_2
09/14/21 Fundamentals: Lower Bounds (the Linear Q* Assumption) & Bellman Completeness Ch.3 Slides_2_continued, Slides_Bellman_complete, Slides_2_continued_annotated, HW1
09/16/21 Fundamentals: Linear Bellman Completion (Continue) Ch.3 Slides, Annotated Slides
09/21/21 Fundamentals: Fitted Dynamic Programming Ch.4 Slides, Annotated Slides
09/23/21 Exploration: Multi-armed Bandits / Linear Bandits Ch.6 Slides, Annotated Slides
09/28/21 Exploration: Linear Bandits Ch.6 Slides, Annotated slides
09/30/21 Exploration: Efficient Exploration in Tabular MDPs Ch.7 Slides, Annotated Slides
10/5/21 Exploration: Efficient Exploration in Linear MDPs Ch.8 Slides, Annotated Slides
10/7/21 Exploration: Linear MDP (continue) Slides, Annotated Slides
10/12/21 No class
10/14/21 Exploration: Learning in Large Scale MDPs (Bellman rank) Ch.9 Slides, Annotated Slides
10/19/21 Exploration: Learning in Large Scale MDPs (Bellman rank Continued) Slides, Annotated Slides
10/21/21 Policy Optimization: Policy Gradient and Convergence Ch.11 Slides, Annotated Slides, HW2
10/26/21 Policy Optimization: Global Convergence Ch.12 Slides, Annotated Slides
10/28/21 Policy Optimization: Natural Policy Gradient (NPG) and its Global Convergence Ch.12 Slides, Annotated Slides
11/2/21 Policy Optimization: NPG and Function Approximation Ch.12 Slides, Annotated Slides
11/4/21 Policy Optimization: Function Approximation Ch.13 Slides, Annotated Slides
11/9/21 Control: Linear Quadratic Regulators (LQRs) Ch.16 Slides, Annotated Slides
11/11/21 Control: Convex parameterization for linear systems and online control Ch.16 Slides, Annotated Slides
11/16/21 Offline RL: Recent Advancements in Offline RL Slides, HW3
11/18/21 Imitation Learning: Behavior Cloning and Distribution Matching Slides
11/23/21 Imitation Learning: Interactive Imitation Learning Slides
11/25/21 No class
11/30/21 No class
12/2/21 No class
12/7/21 Student Project Presentations
12/9/21 Student Project Presentations