Reinforcement Learning

Personal study notes written in my own words from publicly available lectures and course pages. Not affiliated with or endorsed by Stanford University. No assignment solutions are published here.

What the course is about

Reinforcement learning is the study of an agent that must choose actions over time, sees only the consequences of what it actually tried, and is judged by a reward that may arrive long after the decision that earned it. That combination of sequential decisions, delayed credit, and self-generated data separates it from supervised learning, where the dataset is fixed and every example comes with the right answer. CS234 builds the subject from the ground up: first the mathematical model of a decision problem, then how to plan when the model is known, then how to learn when it is not, and finally how to make all of that work with neural networks, limited data, and human preferences.

You should be comfortable with probability, expectations, basic linear algebra, and gradient-based optimization at the level of an introductory machine learning course. Familiarity with supervised deep learning helps for the second half but is not assumed for the first.

The lectures follow a clear arc. The tabular material (MDPs, dynamic programming, Monte Carlo, temporal-difference learning, Q-learning) establishes the ideas exactly. Function approximation and deep Q-learning show what breaks when tables are replaced by parameters and what fixes exist. Policy gradient methods offer a second route that optimizes the policy directly. The remaining lectures are about the questions that matter once the basic machinery works: how to explore, how to learn from other people’s data, how to plan with a learned or simulated model, how to align a language model with human feedback, and when reinforcement learning is simply the wrong tool.

Lecture notes

01 · What reinforcement learning is

An RL agent lives in a loop: observe a state, pick an action, receive a reward and a next state, repeat. The goal is a policy, a rule mapping states to actions, that maximizes the expected sum of rewards over the whole interaction. Three features make this harder than fitting a classifier. Decisions are sequential, so an action changes which future states you get to see. Reward is delayed, so the credit for a good outcome has to be spread back over many earlier choices. And the data is generated by the agent’s own behavior, so it must explore actions that look bad now in case they turn out well, while still exploiting what it already knows.

Compare the settings you will meet in this course:

The usual failure at this stage is conceptual: treating reward as a label. Reward tells you how good the action you took was, not what the best action would have been. Everything that follows is machinery for recovering “what should have been done” from “how did that go”.

The next lecture makes the environment precise with a Markov decision process, which is what lets the credit-assignment problem be written as a set of equations.

02 · Markov decision processes and Bellman equations

A Markov reward process is a set of states, a transition distribution $P(s' \mid s)$, a reward function $R(s)$, and a discount $\gamma \in [0,1)$. The Markov property says the next state depends only on the current one, not the history. The return from time $t$ is $G_t = \sum_{k \ge 0} \gamma^k r_{t+k}$, and the value of a state is its expected return, $V(s) = \mathbb{E}[G_t \mid s_t = s]$. A Markov decision process adds actions: transitions become $P(s' \mid s, a)$ and rewards $R(s, a)$. A policy $\pi(a \mid s)$ turns an MDP back into an MRP.

Because the return is recursive, so is the value. The Bellman expectation equation for a fixed policy is

and the Bellman optimality equation, which characterizes the best achievable value, is

The action-value $Q^{\pi}(s,a)$ is the same quantity conditioned on the first action, and $V^{\pi}(s) = \sum_a \pi(a \mid s) Q^{\pi}(s,a)$. For a finite MDP with $\gamma < 1$, an optimal deterministic stationary policy exists and acts greedily with respect to $Q^{\star}$.

What goes wrong in practice is usually the modeling step rather than the math. A state that omits information the reward depends on breaks the Markov property, so values become ill-defined. A discount chosen for convergence rather than for the task quietly changes which policy is optimal. Rewards that are easy to write down, such as a bonus for reaching a checkpoint, are often gamed.

With the equations in hand, the next lecture solves them when the model is known.

03 · Planning with dynamic programming

When $P$ and $R$ are known, the Bellman equations can be solved by iteration rather than by interacting with the world. Policy evaluation applies the expectation equation as an update, $V_{k+1} \leftarrow R^{\pi} + \gamma P^{\pi} V_k$, until it stops changing. The update is a contraction in the max norm with modulus $\gamma$, which is why it converges from any starting point and why a smaller discount converges faster.

Policy iteration alternates two steps: evaluate the current policy, then act greedily with respect to $Q^{\pi}$. The policy improvement theorem guarantees the new policy is at least as good in every state, and since there are finitely many deterministic policies the loop terminates at an optimal one, usually in few iterations. Value iteration skips the full evaluation and applies the optimality backup directly, $V_{k+1}(s) \leftarrow \max_a [R(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V_k(s')]$. It converges to $V^{\star}$, and the greedy policy with respect to $V_k$ is typically optimal well before $V_k$ itself has converged.

import numpy as np
# P: (S, A, S) transition tensor, R: (S, A) rewards
def value_iteration(P, R, gamma, iters=500):
    V = np.zeros(P.shape[0])
    for _ in range(iters):
        Q = R + gamma * P @ V          # (S, A)
        V = Q.max(axis=1)
    return V, Q.argmax(axis=1)

The practical obstacle is size. Both methods sweep every state, so they are useless for continuous or combinatorial state spaces. Everything after this lecture is about doing without a known model or without a table, and the first step is estimating values from experience.

04 · Model-free policy evaluation

If the model is unknown, $V^{\pi}$ has to be estimated from trajectories generated by running $\pi$. Monte Carlo evaluation waits until an episode ends, computes the actual return $G_t$ from each visited state, and averages. It is unbiased, needs no Markov assumption, but has high variance because a single return sums many random rewards, and it cannot update mid-episode or in continuing tasks.

Temporal-difference learning replaces the full return with a bootstrapped one-step target. The TD(0) update is

where the bracketed term is the TD error. The target uses the current, possibly wrong, estimate $V(s_{t+1})$, so it is biased, but it has much lower variance and updates after every step. With a decaying step size and every state visited infinitely often, tabular TD(0) converges to $V^{\pi}$. On a fixed batch of episodes the two methods give different answers: Monte Carlo minimizes squared error on observed returns, while TD finds the value of the maximum-likelihood MDP implied by the data.

TD($\lambda$) interpolates between the two by weighting $n$-step returns geometrically; $\lambda = 0$ recovers TD(0) and $\lambda = 1$ recovers Monte Carlo. Eligibility traces make this computable online.

Typical mistakes are a step size that never decays, so the estimate keeps oscillating, and evaluating a policy from data that was not generated by it, which is the off-policy problem treated later. The next lecture turns evaluation into control.

05 · Model-free control

Control means finding a good policy, not just evaluating one. The template is generalized policy iteration: estimate $Q$ for the current policy, then make the policy greedier. Working with $Q$ rather than $V$ matters because choosing a greedy action from $V$ requires the model, while choosing from $Q$ does not. Pure greediness kills exploration, so the standard fix is $\epsilon$-greedy: act greedily with probability $1 - \epsilon$ and uniformly at random otherwise.

SARSA is on-policy: it updates toward the action the current policy actually took next,

Q-learning is off-policy: it updates toward the best next action regardless of what the behavior policy did,

Tabular Q-learning converges to $Q^{\star}$ if every state-action pair is visited infinitely often and step sizes satisfy the Robbins-Monro conditions ($\sum \alpha_t = \infty$, $\sum \alpha_t^2 < \infty$). SARSA converges under the same conditions if $\epsilon$ also decays to zero, a schedule called GLIE (greedy in the limit with infinite exploration).

Common failures are decaying $\epsilon$ too fast, which locks in a poor policy before rare states are seen, and the maximization bias in Q-learning: a max over noisy estimates overestimates, which double Q-learning fixes by using one estimate to choose the action and another to evaluate it. That fix returns in the DQN lecture. First, the tables have to go.

06 · Value function approximation

Real problems have too many states for a table, so the value function becomes a parameterized function $\hat V(s; w)$ of a feature vector. The objective is mean squared error against the true value under the state distribution the policy visits, so gradient descent would step along $[V^{\pi}(s) - \hat V(s;w)] \nabla_w \hat V(s;w)$. Since $V^{\pi}$ is unknown, plug in a target. The Monte Carlo return gives a true gradient method; the TD target $r + \gamma \hat V(s';w)$ gives a semi-gradient, so called because the gradient flows through the prediction but not through the target, which also depends on $w$.

For linear features $\hat V(s;w) = x(s)^{\top} w$, the semi-gradient TD(0) update is $w \leftarrow w + \alpha [r + \gamma x(s')^{\top} w - x(s)^{\top} w]\, x(s)$. On-policy linear TD converges to a fixed point whose error is within a constant factor of the best error achievable in the feature class, with the factor growing as $\gamma$ approaches one.

The cautionary result is the deadly triad: function approximation, bootstrapping, and off-policy training. Any two are fine; all three together can diverge, even with linear features and even for pure evaluation. Off-policy data weights states differently from the distribution the fixed-point analysis assumes, so the bootstrapped target can push parameters in a direction that makes the target itself grow.

Practical failures include unscaled features that make one step size wrong for every component, and forgetting that the error bound holds under the on-policy distribution, so values may be poor in exactly the states a new policy visits. Deep Q-learning lives inside the triad and survives by engineering.

07 · Deep Q-learning

DQN replaces the linear approximator with a neural network that maps a state to a $Q$ value for every action. Two changes make deep Q-learning stable enough to be useful. Experience replay stores transitions $(s,a,r,s')$ in a buffer and trains on random minibatches, breaking the correlation between consecutive samples and reusing each transition many times. A target network is a lagged copy of the parameters, $w^{-}$, refreshed periodically, so the regression target does not move with every update. The loss is

Three refinements are standard. Double DQN addresses the maximization bias from the control lecture by selecting the next action with the online network and evaluating it with the target network, $r + \gamma Q(s', \arg\max_{a'} Q(s',a';w); w^{-})$. Dueling networks split the output into a state value and per-action advantages, $Q = V + A - \text{mean}(A)$, which helps when most actions barely matter in most states. Prioritized replay samples transitions in proportion to their TD error, with importance weights to correct the bias.

Things that go wrong: rewards on wildly different scales (clipping helps but changes the objective), a target update period too short to stabilize anything, and treating a single seed’s score as evidence. DQN also handles only discrete actions. For continuous control, and for a cleaner theoretical story, the course switches to optimizing the policy directly.

08 · Policy gradient

Instead of learning values and acting greedily, parameterize the policy $\pi_{\theta}(a \mid s)$ directly and ascend the expected return $J(\theta) = \mathbb{E}_{\tau \sim \pi_{\theta}}[G(\tau)]$. This handles continuous actions naturally, can represent stochastic policies (sometimes necessary under partial observability), and changes the policy smoothly rather than by the discontinuous jumps a greedy step can make.

The likelihood-ratio trick makes the gradient estimable from samples. Since $\nabla_{\theta} p_{\theta}(\tau) = p_{\theta}(\tau) \nabla_{\theta} \log p_{\theta}(\tau)$, and the transition probabilities do not depend on $\theta$, the policy gradient theorem gives

where $G_t$ is the return from time $t$ onward. REINFORCE is exactly this estimate with Monte Carlo returns: run episodes, weight each log-probability gradient by the return that followed, and step. Using the reward-to-go $G_t$ rather than the whole-episode return is valid because actions cannot affect earlier rewards, and it removes variance for free.

The estimator is unbiased but noisy. Subtracting a baseline $b(s_t)$ that does not depend on the action leaves the expectation unchanged, because $\mathbb{E}_{a \sim \pi}[\nabla_{\theta} \log \pi_{\theta}(a \mid s)] = 0$, yet can reduce variance substantially. The natural choice is a learned state value $\hat V(s_t)$, which turns the weight into an estimated advantage $G_t - \hat V(s_t)$: how much better this action was than the policy’s average.

Failures are almost always variance and step size. Vanilla REINFORCE needs many episodes per update, and a step that is too large can move the policy to a region where every sampled action is bad and recovery is slow, since the data comes from the broken policy. Reducing variance with a critic and constraining step size are the two directions the next lecture takes.

09 · Actor-critic, trust regions, and PPO

An actor-critic pairs a policy (the actor) with a learned value function (the critic) that supplies the baseline and, optionally, a bootstrapped return. Replacing the Monte Carlo return with the one-step TD target gives the advantage estimate $r_t + \gamma \hat V(s_{t+1}) - \hat V(s_t)$, low-variance but biased by critic error. Generalized advantage estimation (GAE) averages $n$-step advantages with exponential weights $\lambda$, the same bias-variance dial as TD($\lambda$). A2C is this recipe with several parallel environments feeding one synchronous update.

The step-size problem has a principled answer. TRPO maximizes a surrogate built from the probability ratio $r_t(\theta) = \pi_{\theta}(a_t \mid s_t) / \pi_{\theta_{\text{old}}}(a_t \mid s_t)$ subject to a bound on the KL divergence between new and old policies. A lower bound on true improvement degrades with that KL distance, so staying close guarantees monotone improvement in the idealized case. The cost is a second-order solve.

PPO gets most of the benefit with first-order updates by clipping the ratio:

The min removes any incentive to push the ratio outside $[1-\epsilon, 1+\epsilon]$ in the direction that raises the objective, so several epochs of minibatch ascent on one batch remain safe. The full loss adds a value-function term and an entropy bonus.

What goes wrong: unnormalized advantages, a critic that lags far behind the actor, and reusing old data past the point where clipping still does anything. Next is a different source of signal entirely: demonstrations.

10 · Imitation learning

When reward is hard to specify but experts are available, learn from their behavior. Behavior cloning is supervised learning on expert state-action pairs: fit $\pi(a \mid s)$ to the expert’s choices. It is simple and often strong, but errors compound. The learner is trained on states the expert visits, makes a small mistake, drifts to a state the expert never saw, and has no idea what to do there. Error grows roughly quadratically with the horizon rather than linearly, because each mistake shifts the distribution of everything after it.

DAgger (dataset aggregation) fixes the mismatch interactively. Run the learner’s current policy, record the states it visits, have the expert label those states, add them to the dataset, retrain, repeat. The learner now trains on its own state distribution, and the error bound becomes linear in the horizon. The price is an expert who can be queried on demand, realistic for a simulator or labeling pipeline and unrealistic for a single recorded dataset.

Inverse reinforcement learning turns the problem around: infer a reward under which the expert’s behavior is near-optimal, then learn against that reward. The reward is underdetermined (many rewards explain the same behavior, including the zero reward), so methods add a preference such as maximum margin or maximum entropy. The appeal is that a reward transfers to new dynamics in a way a cloned policy does not.

The usual mistake is assuming the expert is optimal and consistent; real demonstrations are noisy and multimodal, and a unimodal cloned policy averages across them. Demonstrations reduce the need to explore, which raises the question of how to explore when you must.

11 · Exploration and bandits

The cleanest setting for exploration is the multi-armed bandit: one state, $K$ actions, each with an unknown reward distribution. Performance is measured by regret, the gap between what always pulling the best arm would have earned and what you actually earned. Regret growing sublinearly in $T$ means the learner eventually finds the best arm; logarithmic regret is the benchmark when arms are separated by a fixed gap.

Greedy and $\epsilon$-greedy fail this test: greedy can lock onto a bad arm forever, and a fixed $\epsilon$ pays linear regret from random pulls. Optimism in the face of uncertainty does better. UCB1 pulls the arm that maximizes an upper confidence bound,

where $\hat\mu_a$ is the empirical mean and $N_a$ the pull count. Rarely tried arms get a large bonus; as evidence accumulates the bonus shrinks and the estimate dominates. The bonus comes from a concentration inequality, and the resulting regret is logarithmic in $T$.

Thompson sampling is the Bayesian alternative: keep a posterior over each arm’s mean, draw one sample per arm, and pull the arm with the largest sample. It explores in proportion to the probability that an arm is actually best, is trivial for Bernoulli rewards with Beta priors, and is competitive with UCB in practice.

The same optimism principle scales to MDPs. Model-based methods that add bonuses for rarely visited state-action pairs achieve polynomial sample complexity, whereas $\epsilon$-greedy can take exponentially long on chain-like environments. In deep RL the idea survives as count-based bonuses on learned state features and as value-function ensembles that approximate a posterior.

Mistakes to avoid: reading regret bounds as performance guarantees at small $T$, and reusing a bonus scale tuned for one reward range on another. Exploration presumes you may act in the world; the next lecture drops that assumption.

12 · Offline RL and off-policy evaluation

In healthcare, education, and many industrial settings you cannot run a new policy to see how it does. You have a log of trajectories collected by a behavior policy $\pi_b$, and you want to estimate the value of a proposed policy $\pi_e$, or learn a better one, without deploying anything. This is offline (batch) RL, and off-policy evaluation is its central problem.

Importance sampling reweights logged returns by how much more likely $\pi_e$ was to produce the observed trajectory than $\pi_b$:

It is unbiased when $\pi_b$ is known and puts positive probability on every action $\pi_e$ might take, but the product of ratios has variance that grows exponentially with the horizon. Per-decision importance sampling applies to each reward only the ratios up to that time; weighted (self-normalized) importance sampling trades a small bias for much lower variance.

A direct method fits $Q$ or a dynamics model from the log and reads off the value, with low variance but whatever bias the model has. The doubly robust estimator uses the model as a baseline and corrects it with importance-weighted residuals. It is unbiased if either the model or the behavior policy is correct, and its variance is usually far below plain importance sampling.

For learning offline, the danger is extrapolation: Q-learning assigns high value to actions the log never contains, then chooses them. Offline algorithms constrain the policy toward the behavior policy or penalize unsupported actions. The stakes are real because a treatment or tutoring policy may be deployed once, with no chance to recover. Planning with a model, when one exists, is a very different way to spend computation.

13 · Monte Carlo tree search and AlphaZero

When a simulator or known model is available, planning at decision time can substitute for a global value function. Monte Carlo tree search grows a tree from the current state through four repeated steps: select a path down the tree using a bandit rule at each node, expand a new leaf, evaluate it (originally by a random rollout to the end of the game), and back up the result along the path. The selection rule is a UCB variant on tree nodes, so the optimism principle from the bandit lecture decides which lines of play get more simulation. Effort concentrates on promising moves without enumerating the game tree, and you can stop whenever the clock says so.

AlphaZero-style planning replaces two weak pieces of classic MCTS. Random rollouts give way to a neural network that evaluates a leaf position directly, and the uniform move prior gives way to a policy head that biases selection toward plausible moves through a PUCT rule that scales the exploration bonus by the prior. The search then improves on the network: root visit counts form a better move distribution than the raw policy head, and the game outcome is a better target than the raw value head. Training is self-play: play games with search, then regress the network toward the search’s move distribution and the final outcome. Search acts as a policy improvement operator and the network distills it, so each iteration raises both.

Where it goes wrong: MCTS needs a model that can be queried cheaply and exactly, which board games provide and most real environments do not. Stochastic or partially observed settings complicate the tree. And self-play learns against itself, which an opponent playing outside that distribution can exploit. Learning from a model of human preferences rather than a game outcome is the last major topic.

14 · Reinforcement learning from human feedback

Language models are pretrained to predict text, which is not the same as being helpful. RLHF turns human judgments into a training signal in three stages. First, supervised fine-tuning on demonstrations. Second, collect pairs of responses to the same prompt, ask annotators which is better, and fit a reward model $r_{\phi}(x, y)$ to the comparisons with the Bradley-Terry likelihood, $P(y_1 \succ y_2) = \sigma(r_{\phi}(x,y_1) - r_{\phi}(x,y_2))$. Third, treat the language model as a policy that generates a response given a prompt and optimize it against the reward model, in practice with PPO.

The objective is KL-regularized:

The KL term keeps the policy near the reference model it started from. Without it, the policy over-optimizes a reward model that is only accurate near its training data, and outputs degrade into whatever quirks the reward model scores highly. Reward hacking is the default outcome of running RL against a learned reward for long enough.

Direct preference optimization (DPO) observes that this objective has a closed-form optimum, $\pi^{\star}(y \mid x) \propto \pi_{\text{ref}}(y \mid x) \exp(r(x,y)/\beta)$, so the reward can be expressed through the policy and the reference model. Substituting into the Bradley-Terry loss gives a classification-style loss on preference pairs that trains the policy directly, with no explicit reward model and no sampling during training. It trades PPO’s on-policy exploration for simplicity.

The recurring problems are annotator disagreement and bias baked into the reward model, length and style preferences the policy learns to exploit, and evaluating with the same reward model you optimized against. All are instances of one question: when does optimizing a proxy make things worse?

15 · Safe and fair RL, and when RL is the wrong tool

Two properties matter for any RL system that acts on people. Safety asks that the policy not cause harm during learning or deployment: constrained MDPs keep expected cost under a budget, conservative updates require high-probability improvement over a baseline before a new policy is switched in, and off-policy evaluation with confidence intervals says how uncertain an estimate is. Fairness asks how outcomes are distributed across groups, which the sequential setting complicates: an action that looks fair now can shift which states different groups reach later.

The last lecture also covers judgment. RL is a good fit when decisions genuinely affect future states, when a reward can be specified or learned that captures what you want, when interaction is cheap to gather or simulate, and when a bad action during learning is tolerable. It is the wrong tool when a supervised model or a bandit would answer the question with far less data, when the reward is a proxy that can be gamed, when the environment cannot be simulated and mistakes are irreversible, or when the appearance of an agent learning matters more than the decisions it will make.

The theme of the course is that every method buys something with something else: TD buys variance with bias, function approximation buys generalization with stability, off-policy learning buys data reuse with divergence risk, and learned rewards buy flexibility with the risk of optimizing the wrong thing. Knowing which trade you are making is most of the skill.

Key equations at a glance

Common mistakes

• Treating reward as a label for the action taken. Reward says how the chosen action went, not which action was best; use a control method, not a classifier, unless you actually have expert labels.
• Decaying $\epsilon$ or the step size too fast in tabular methods. The convergence guarantees need every state-action pair visited infinitely often and $\sum \alpha_t = \infty$; a schedule that shuts off exploration early converges to the wrong thing.
• Trusting a max over noisy $Q$ estimates. The maximization bias inflates values; use double Q-learning or double DQN and check whether predicted values track actual returns.
• Combining bootstrapping, function approximation, and off-policy data without a stabilizer. That is the deadly triad; add a target network, keep data close to on-policy, or use a method designed for offline data.
• Running many epochs of policy gradient on a single batch with no ratio constraint. The gradient estimate is only valid near the policy that collected the data; use PPO clipping or a KL penalty and few epochs.
• Cloning demonstrations and evaluating only on expert states. Compounding error shows up on the learner’s own state distribution; evaluate by rolling out the policy, and use DAgger if the expert can be queried.
• Using plain importance sampling over long horizons. The product of ratios makes the estimator useless beyond a few dozen steps; switch to per-decision, weighted, or doubly robust estimators and report confidence intervals.
• Optimizing a learned reward model without regularization. The policy finds inputs where the reward model is wrong; keep the KL term, hold out an independent evaluation, and inspect samples rather than only scores.

Related courses

• CS229 supplies the probability, optimization, and supervised-learning foundations that policy evaluation and function approximation build on.
• CS230 covers the deep-learning training practice (optimizers, initialization, debugging) that DQN and PPO depend on.
• CS231n is where the convolutional encoders used for pixel-based agents come from.
• CS224n explains the language models that RLHF fine-tunes and the sequence-model view of a policy over tokens.
• CS336 goes deeper into the systems and post-training side of language models, including preference optimization at scale.
• CS246 treats bandits and online learning from the data-mining side, complementing the exploration lecture here.