CS 639: Introduction to Reinforcement Learning

Course Information

Course Description

This is a senior/master's-level introduction to reinforcement learning (RL): making good decisions in sequence, when each decision changes what happens next. The course covers the framework (Markov decision processes) and the core algorithms, from value iteration to RLHF: how each is designed, why it works, and when it fails. Algorithms are derived on the board, a few central theorems are proved in full, and the homework has you implement the algorithms and run them on small problems. Topics include (tentative):

• Planning in tabular MDPs: value functions, Bellman equations, value iteration, policy iteration
• Learning in MDPs: Monte Carlo, temporal-difference learning, SARSA, Q-learning, importance sampling, linear function approximation
• Function approximation and policy optimization: DQN, policy gradient, actor-critic, PPO
• Data regimes and outcome-based feedback: offline RL, exploration, imitation learning, RLHF / DPO / RLVR, model-based RL and search

Schedule

Grading

There is no project and no final exam. Three kinds of graded work:

• Homework: 40% (four programming-focused homeworks, 10% each; HW0 is required but not graded)
• Six in-class quizzes: 30% (6% each; the best 5 of 6 count)
• One in-class midterm: 30% (currently scheduled for the last week of October)

Quizzes. About 15 minutes at the start of class, closed book, announced one or two lectures in advance. The best 5 of 6 count, so there are no make-ups.

Midterm. In class, 75 minutes, covering the first half of the course. More details before the midterm.

Homework. HW0 is a readiness self-check on the prerequisites, out Sep 03 and due Sep 11: everyone enrolled must submit it, but it does not count toward the grade. The four homeworks are programming-focused, in Python (NumPy first, PyTorch later). Submit on Gradescope.

Late Homework Policy

HW1-HW4 share 4 slip days, with at most 2 used on any one assignment. Slip days are applied automatically from the submission timestamp; no request and no reason are needed.

Every assignment closes 48 hours after its deadline, and solutions are released then. Late time not covered by slip days costs 10% of the maximum score per started 24-hour period, counted the same way. After the hard close the score is 0.

Slip days do not apply to HW0 (required but not graded), to quizzes (the best 5 of 6 count instead), or to the midterm. Documented emergencies, disability accommodations, and religious observance are handled by the instructor outside the slip-day budget; please reach out.

Prerequisites

Students should be comfortable with:

• Probability and statistics (probability review)
• Linear algebra, calculus, and basic algorithms (linear algebra review)
• Programming in Python with NumPy (tutorial)
• An introductory machine-learning course (regression, loss functions, gradient descent)

Deep learning is not assumed at the start: the second half of the course uses PyTorch at a basic level, and warm-up material will be released before HW3. Prior exposure to reinforcement learning is not required. HW0 is a readiness check on this background. If parts of it feel unfamiliar, start with the review material linked above and reach out early.

Academic Integrity and Collaboration Policy

Homework must be your own work. You may discuss ideas and debugging approaches with at most two named classmates, but you must write every proof, every line of code, and every plot yourself, and every submission lists its collaborators and sources. Quizzes and the midterm are individual work.

Cheating and plagiarism will be dealt with in accordance with University procedures (see the UW-Madison Academic Misconduct Rules and Procedures). If you have any questions about this policy, please ask the instructor before you act.

AI Policy

Each assignment carries a traffic-light label for the use of generative AI tools (ChatGPT, Claude, Gemini, Copilot, and others):

• Green: free use, e.g., for self-study and extra practice.
• Yellow: limited, disclosed use; the default for programming parts. Never for the core update rule, proof, or analysis you are asked to produce.
• Red: no AI. Quizzes, the midterm, and problems marked as individual derivation checks.

Every submission includes an Assistance Statement, and you must be able to explain everything you submit. Use beyond an assignment's label is a violation of the course's expectations and will be addressed through UW-Madison's academic misconduct policy.

Resources

• Reinforcement Learning: An Introduction (2nd ed., PDF) by Sutton and Barto: the companion text
• Reinforcement Learning: Theory and Algorithms by Agarwal, Brantley, Jiang, Kakade, and Sun (optional, deeper)
• Algorithms for Reinforcement Learning by Szepesvári (optional, deeper)