CS 1840: Introduction to Reinforcement Learning

Syllabus

Introduction

Modern 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 high-level performance in challenging applications such as Go, computer games, robotic manipulation, health care, education, and the training of large language models.

This course provides an introduction to reinforcement learning covering a range of problem formulations, algorithms, and theory. The five main themes of the course are:

1. tabular planning (the Markov decision process formalism, Bellman equations, policy evaluation, value iteration, policy iteration),
2. exploration (multi-armed bandits, regret, explore-then-commit, epsilon-greedy, upper confidence bounds, contextual bandits),
3. value-based learning (temporal-difference learning, Q-learning, tabular model-based RL and the simulation lemma, function approximation, deep Q networks),
4. imitation learning (behavior cloning, DAgger), and
5. policy optimization (REINFORCE, variance reduction, natural policy gradient, PPO, learning from human feedback and from verifiable rewards).

There will also be an Embedded Ethics lecture on ethical issues arising in reinforcement learning.

The assignments will focus on a mix of algorithmic and statistical principles, along with their programming implementations. After taking this course, students will be able to state, implement, and analyze the fundamental RL algorithms.

Staff and organization

Head instructor: Kianté Brantley

TFs: Alex Dazhen Cai (Head TF), Egil Rolstad, Philip Nielsen

CAs: Emmanuel Rassou, Justin Li, Ishaan Sinha

Lecture time: Monday/Wednesday 11:15am–12:30pm

Lecture location: 114 Western Ave 2111–2112

Sections and office hours: These are optional and start in the second week of classes. See the table below for the weekly schedule. The section cycle starts on Mondays and covers the material from the last week's two lectures.

Calendar: Please double check the course Google Calendar below for the most up-to-date information on location changes and cancellations.

Discussion: We will use an Ed discussion forum for course communication including announcements and homework clarifications. Ed allows private posts that are only visible to you and the teaching staff (not your classmates). Do not email course staff except in the case of sensitive requests such as Disability Access Office accommodations or personal emergencies. These should be sent directly to the head instructor and head TF.

Prerequisites

We assume background in:

• calculus & linear algebra (e.g. AM22a, Math 21b);
• probability theory (e.g. Stat 110);
• programming in Python (e.g. CS 50, CS 32).

Homework zero (HW0) checks your familiarity with these topics. If you find it challenging, please come to office hours to meet with the course staff.

The following topics are recommended but not required:

• linear regression (e.g. Stat 139);
• supervised learning (e.g. CS 1810, Stat 195);
• algorithms (e.g. CS 1200).

Assessments and grading

The course is letter-graded by default, but you may switch to SAT/UNSAT if you prefer. Your final grade will be calculated as a weighted average of course assessments:

Participation

Participation: You can demonstrate participation in the course in many different ways:

• regular attendance of lectures
• attending sections and office hours
• asking questions on the Ed forum

At the end of the term, you will submit a paragraph on how you participated in the course. Regularly attending lectures will suffice for a full participation grade. If you have another responsibility that prevents you from attending all the lectures, please make a private post on Ed at the beginning of the semester, and we will expect increased engagement through sections and Ed.

Homework

Homework materials: Homework assignments can be downloaded from Canvas. There are five homeworks, released every two weeks; You will have an additional week for HW3 to help prepare for the midterm and an additional week for HW5 since it is a more open-ended assignment. Each homework contains a math portion and a programming portion.

1. For the math portion, you must submit a single PDF. You may choose to neatly handwrite your work or typeset it using a markup language such as LaTeX or Typst. See overleaf.com/learn or typst.app/docs/tutorial for the respective tutorials.
2. For the programming portion, you will submit a zip archive of your codebase in the same file structure as the downloaded assignment. This includes your README.md file with any written responses. See markdownguide.org/getting-started for a guide to Markdown formatting. You do not need to submit a PDF for this portion. If you typeset the math portion, you must include the source code in your zip archive for verification purposes.

Compute requirements: The programming assignments are designed to be runnable on a personal laptop. We will also provide access to cloud CPUs through HUIT. Further information and setup instructions will be posted on Ed.

Homework submission: Homeworks will be submitted through Gradescope. Pages must be correctly assigned to questions in order to be graded.

Late homeworks: Each student will have 96 cumulative hours of late time (as measured on Gradescope). Up to 48 hours may be used on any one assignment. Assignments turned in within 24 hours of the end of usable late hours will receive a 25% deduction from the original grade. Assignments turned in within the following 24 hours will receive another 25% deduction, past which a grade of zero will be given.

Regrade requests: All regrade requests must be submitted on Gradescope within seven days after the grades for the homework in question are released. This ensures that we can address concerns in a timely and fair manner. Grades will only be changed in the case of a clear mis-application of the rubric.

Homework grading: HW0 is graded on completion (effort shown, not correctness). For the remaining homeworks 1–5, each question is worth some indicated number of points, and your final homework score will be a weighted average across all homework questions with respect to these points. In order to pass the course, you must attempt and submit all homeworks, even for zero credit.

Collaboration: Collaboration is encouraged under the restriction that you fully own your submissions and cite any help you received. This means that when you submit a homework, you affirm that:

• The entirety of your submission was written by you. Including output from a peer or an AI tool into your submission is strictly prohibited.
• Your submission honestly represents your own understanding of the material. If a teaching staff member asks you about any part of your submission and finds that it is not your own work, it will be treated as academic misconduct.
• You have not shared, and will not share, any part of your submission as-is with a classmate or outside of the class. For example, you may not look at a peer's submission or post your solution publicly on Ed. (Discussing your thought process or asking questions is welcome and encouraged.)

In each of your answers, you must list all your collaborators (human or AI), as well as any materials that you consulted (except those on the course website). To support your recall, we recommend you wait a day between receiving help and writing up your own answer.

Exams

Midterm: There will be an in-class midterm on Monday 26 October that covers material up to and including the lecture on Wednesday 21 October. No section will be held that week.

Final exam: The final exam is cumulative and may test knowledge from any material covered in lecture. It will take place between 10–19 December. The exact date and time will be scheduled by the FAS Registrar and announced through Ed. Please do not make travel plans that conflict with the exam period until the exam date is announced.

Diversity and Inclusion

Many academic disciplines have historically been dominated by one cross-section of society. However, the study of and participation in STEM disciplines is a joy that the instructors hope everyone can pursue, regardless of their background and identity. We 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!

We are committed to Harvard's Community Values. You should expect to be treated by your classmates and the course staff with respect. You belong here, and we are here to help you learn and enjoy this course. If any incident occurs that challenges this commitment to a supportive and inclusive environment, please let the course staff know so that the issue can be addressed.

We encourage you to familiarize yourself with Harvard's Non-Discrimination and Anti-Bullying (NDAB) Policies and Title IX policies. In particular, all course staff are Responsible Employees and are obligated to report possible cases of sexual misconduct to an FAS Title IX Resource Coordinator.

We encourage you to take advantage of Harvard's support resources, including the following:

• Academic Resource Center
• Mignone Center for Career Success
• Counseling and Mental Health Resources

Harvard University values inclusive excellence and providing equal educational opportunities for all students. Our goal is to remove barriers for disabled students related to inaccessible elements of instruction or design in this course. If reasonable accommodations are necessary to provide access, please contact the Disability Access Office (DAO). Accommodations do not alter fundamental requirements of the course and are not retroactive. Students should request accommodations as early as possible, since they may take time to implement. Students should notify DAO at any time during the semester if adjustments to their communicated accommodation plan are needed. If you are registered for testing accommodations, please schedule your midterm exam through the FAS Testing Center Pilot.

Honor code and AI policy

You are held to the Harvard College Honor Code. See the section above on collaboration. To further elaborate:

• Do not use forums like Course Hero, Chegg, etc.
• Do not directly ask or search for answers, either from a peer, on the Internet, or from an AI tool.
• Properly cite any outside materials you use for your homeworks. If you are unclear about whether some online material can be used, please ask the course staff first.
• Do not share of your solutions within or outside class at any time.
• The same principles apply to generative AI tools as human collaborators: you can use them for assistance, and if you do, you should cite them, but you may not directly ask them for the answer.

The above is not an exhaustive list, and in general, common sense rules about academic integrity apply. If something is in doubt, please ask us for permission before you do it.

Course materials

Lecture slides: Slides will be posted before each lecture, and annotated slides (with all notes taken on them by the instructor during lecture) will be posted after each lecture.

Lecture recordings: Individual lecture recordings will be made available upon request through this Google Form. Access will be unconditionally granted one day after the request. It is possible that some lectures may not be recorded, in which case we will not be able to do a make-up lecture. We encourage you to attend lectures in person and participate in class discussion.

Section materials: Section materials and solutions will be posted by TFs on the course materials spreadsheet.

Textbooks: There are many high-quality open resources available that intersect with our course material. This reading is strictly supplementary: course assessments will be based solely on material covered in lectures and homeworks.

• rlbook: An Introduction to Reinforcement Learning by Alex Cai. This is a draft textbook for the course that should closely follow the lecture content, notation, and structure, with some additional material and examples. Feedback is welcome and appreciated via the Ed forum.
• S&B: Reinforcement Learning: An Introduction by Richard Sutton and Andrew Barto. This is the classic text in reinforcement learning.
• ABJKS: Reinforcement Learning: Theory and Algorithms by Alekh Agarwal, Kianté Brantley, Nan Jiang, Sham Kakade, and Wen Sun. This is an advanced RL theory book that is mostly out of the scope of this class. Feedback is encouraged and should be sent to bookrltheory [at] gmail [dot] com.

Schedule

You may need to scroll to the right to see details.