Foundations
Tabular RL end to end, from bandits to policy gradients, with an exercise after each idea. Read a station, then do the exercise that follows it before moving on.
What you will learn
Orientation gave you the vocabulary and the sources but no algorithms. Every deep method later on is a tabular idea plus a function approximator, and a reader who skipped the tabular version cannot tell which half of a deep agent is failing.
Tabular RL end to end: bandits and regret, MDPs and dynamic programming, Monte Carlo and TD estimation, Q-learning and SARSA for control, Dyna for planning, n-step returns and eligibility traces, then the two cliffs, partial observability and the deadly triad, and the first policy gradient. An exercise follows each idea so that the implementation, not the reading, is what gets checked.
You can implement any tabular method from its update rule, predict how two of them will differ on a task before running them, and explain why bootstrapping, off-policy data and approximation are dangerous together.
Auer et al. 2002; Jaksch, Ortner & Auer 2010; Lattimore & Szepesvári 2020
UCB, Thompson Sampling, Bandit Algorithms
Regret in the one-state case: optimism (UCB) and posterior sampling (Thompson). Lattimore & Szepesvari is the companion book. Regret in unknown MDPs is a separate problem — it lives on the Exploration track.
Foundational to exploration. UCRL2 extends this from bandits to unknown MDPs.
Learning outcome: Derive the UCB bonus, implement UCB and Thompson sampling, and plot cumulative regret against a fixed baseline.
Resources
- Auer et al. 2002, UCB (paper)
- Lattimore & Szepesvári, Bandit Algorithms (PDF) (book, optional)
- Silver lecture 9: Exploration and Exploitation (video)
- CS234 lecture 11: Exploration 1 (video)
Sutton & Barto ch. 3–4
Finite MDPs, Bellman equations, dynamic programming
Policy and value iteration. The Bellman optimality operator.
Underlies every value-based method through to MuZero and CQL.
Learning outcome: Write the Bellman expectation and optimality equations for a small MDP and say why value iteration converges.
Resources
- Ch. 3 Finite Markov Decision Processes (chapter)
- Ch. 4 Dynamic Programming (chapter)
- Silver lecture 2: Markov Decision Process (video)
- Silver lecture 3: Planning by Dynamic Programming (video)
- Spinning Up Part 1: Key Concepts in RL (site, optional)
- CS285 lecture 4: Introduction to Reinforcement Learning (6 parts) (video)
- Bootcamp 1: Intro to MDPs and Exact Solution Methods (Abbeel) (video)
- CS234 lecture 2: Tabular MDP Planning (video)
Deliverable: code, a plot, a conclusion
Solve an MDP by hand, then by machine
Write down a four-state MDP, solve it with pencil and paper, then reproduce the answer with code. Disagreement between the two is the point: it is always your understanding or your indexing, and finding out which is the exercise.
Every later implementation rests on getting this arithmetic right.
Learning outcome: Solve a small MDP both ways and explain any disagreement between them.
Prerequisites
Resources
Exercise deliverables
- A four-state MDP written out in full: v_pi for a fixed policy and v_star, by hand
- Policy iteration and value iteration on FrozenLake agreeing with each other to 1e-8
- A plot of max-norm error against sweep, and one sentence on the convergence rate you observe
Sutton & Barto ch. 5
Monte Carlo methods
Estimate values from complete returns.
MC return estimation reappears in REINFORCE and in GRPO's group-relative returns.
Learning outcome: Estimate a value function from complete returns and say when a Monte Carlo estimate is unbiased.
Resources
- Ch. 5 Monte Carlo Methods (chapter)
- Silver lecture 4: Model-Free Prediction (video, optional)
Sutton & Barto ch. 5.5-5.9
Off-policy prediction via importance sampling
Reweight returns collected under a behaviour policy to estimate values under a target policy. Ordinary importance sampling is unbiased with unbounded variance; weighted importance sampling trades a little bias for much less of it.
The same ratio comes back as PPO's probability ratio, V-trace's clipped ratios, off-policy evaluation, and the implicit reward ratio in DPO.
Learning outcome: Derive the ratio for a trajectory, say why its variance grows with the horizon, and recognise it when it reappears in a deep RL objective.
Prerequisites
Resources
- Ch. 5.5-5.9 Off-policy prediction via importance sampling (chapter)
- IMPALA: the same ratio, clipped (V-trace) (paper, optional)
Sutton & Barto ch. 6; Sutton, Machine Learning 1988
Temporal-difference learning
The single most important idea in the field. The bootstrapped target.
Ancestor of the DQN loss.
Learning outcome: Write the TD(0) update and explain the bias it introduces relative to Monte Carlo.
Deliverable: code, a plot, a conclusion
Compare Monte Carlo and TD on one prediction task
Run both estimators against a known ground-truth value function and watch the bias-variance trade-off happen rather than reading about it.
The same trade-off reappears as n-step returns, GAE's lambda and every choice of target in deep RL.
Learning outcome: Say which estimator you would pick for a given task and horizon, from your own measurements.
Prerequisites
Exercise deliverables
- Monte Carlo and TD(0) prediction on the same task, against a known v_pi
- RMS error against episodes for both, over several step sizes and at least 10 seeds
- A paragraph on which wins when, in bias and variance terms
Watkins & Dayan, Machine Learning 1992 (Watkins thesis 1989)
Q-learning
Off-policy TD control with a convergence proof. Skim the original.
Becomes DQN when you swap the table for a neural net.
Learning outcome: Implement Q-learning and say why it is off-policy.
Resources
Rummery & Niranjan 1994; named by Sutton 1996; S&B ch. 6
SARSA
On-policy control.
The on-policy vs off-policy distinction structures the whole field (PPO vs SAC).
Learning outcome: Implement SARSA and Expected SARSA and predict how each behaves near a cliff.
Resources
- Ch. 6.4 Sarsa (chapter)
- Ch. 6.6 Expected Sarsa (chapter)
- Silver lecture 5: Model-Free Control (video, optional)
Deliverable: code, a plot, an explanation
SARSA and Q-learning on the cliff
The two algorithms learn different policies on the same task. Predict the difference before you run it, then check whether your prediction was right and why.
On-policy versus off-policy control is the fork that eventually separates PPO from DQN.
Learning outcome: Explain, from your own runs, why the on-policy agent walks the safe path and the off-policy agent walks the edge.
Prerequisites
Resources
Exercise deliverables
- SARSA, Expected SARSA and Q-learning on CliffWalking in one codebase
- Episode-return curves for all three, over at least 10 seeds, plus the greedy paths they learn
- A written explanation of the difference, and what happens to it as epsilon goes to zero
Sutton, 1990/1991
Dyna
Integrate learning, planning and acting: use a learned model to generate synthetic experience and update the same value function you update from real experience. In the tabular case the model is a table of observed transitions.
The first taste of model-based RL. Imagined rollouts scale up into MBPO and Dreamer.
Learning outcome: Say how many planning steps buy how much sample efficiency on a gridworld, and where the synthetic data starts to hurt.
Prerequisites
Sutton & Barto ch. 7 & 12
n-step bootstrapping and eligibility traces
n-step returns and TD(λ).
n-step returns are a Rainbow component and reappear in R2D2, DreamerV3 and BBF. TD(λ) is the conceptual root of GAE.
Learning outcome: Pick n or lambda for a given task and justify it in bias-variance terms.
Resources
- Ch. 7 n-step Bootstrapping (chapter)
- Ch. 12 Eligibility Traces (chapter)
POMDPs, histories and belief states
Partial observability
An observation is not a state. When the observation does not summarise the history, the Markov property fails and a memoryless policy cannot be optimal. The fixes are all forms of remembering: frame stacking, recurrence, or an explicit latent state.
Why R2D2 is recurrent, why world models learn a latent state, and why agentic LLM RL is framed as a POMDP rather than an MDP.
Learning outcome: Decide whether a given environment is partially observed, and choose between stacking, recurrence and a learned latent state with a reason.
Resources
Sutton & Barto ch. 9–11
Function approximation and the deadly triad
On-policy and off-policy function approximation. Bootstrapping, off-policy updates and function approximation together — the deadly triad — can make value estimates unstable or divergent. All three are present in most deep RL agents that work, so the triad is a risk to manage, not a prohibition.
Explains why DQN needed target networks and replay, and why offline RL is hard.
Learning outcome: Name the three ingredients, say which one you could drop in a given agent, and predict where instability will show up in a learning curve.
Resources
- Ch. 9 On-policy Prediction with Approximation (chapter)
- Ch. 10 On-policy Control with Approximation (chapter)
- Ch. 11 Off-policy Methods with Approximation (chapter)
- Baird's counterexample (1st ed.) (site, optional)
- Silver lecture 6: Value Function Approximation (video)
- CS285 lecture 7: Value Function Methods (4 parts) (video)
- Bootcamp 2: Sample-based Approximations and Fitted Learning (Duan) (video)
Deliverable: code, a plot, a diagnosis
Build a divergence, then stop it
Reproduce Baird's counterexample and watch the weights leave. Then remove one leg of the triad at a time and record which removals rescue it.
You will recognise this failure mode in a deep agent, where it is much harder to see.
Learning outcome: Diagnose an unstable value function by identifying which leg of the triad is doing the damage.
Prerequisites
Exercise deliverables
- Baird's counterexample reproduced, with weights diverging
- A plot of the same setup with one ingredient removed at a time (on-policy sampling, bootstrapping, function approximation)
- A paragraph naming which removals fixed it and which did not, and why
Sutton & Barto ch. 13
Policy-gradient methods
Parameterise the policy directly and follow the gradient of expected return.
Bridge into Phase 3.
Learning outcome: Derive REINFORCE and say why policy gradients handle continuous actions that value methods cannot.
Resources
- Ch. 13 Policy Gradient Methods (chapter)
- Silver lecture 7: Policy Gradient Methods (video, optional)
Deliverable: code, a plot, a derivation
Measure what a baseline buys
Estimate the variance of the policy-gradient estimator with and without a baseline, on the same task and the same samples. Then show on paper that subtracting a state-dependent baseline leaves the estimator unbiased.
Everything from A2C to GRPO is an argument about what the baseline should be.
Learning outcome: Quantify the variance reduction a baseline gives, and prove it costs no bias.
Prerequisites
Exercise deliverables
- REINFORCE with and without a value baseline on one task
- Empirical variance of the gradient estimate for both, plotted against training
- A short derivation that the baseline leaves the gradient unbiased