Lecture 04 · Part 1

Introduction to RL

The formal foundation for everything that follows. Levine defines Markov chains, MDPs, and POMDPs, writes down the RL objective as an expectation under the trajectory distribution, and shows why expectations make even discontinuous rewards optimizable. Then the three-box anatomy shared by every RL algorithm, value functions and Q-functions, and a guided tour of the algorithm zoo — with the trade-offs that explain why so many algorithms exist at all.

▶ Lecture videos (6 parts) Slides (current revision, PDF) ↗

From imitation to rewards

Imitation learning trained a policy $\pi_\theta(a_t \mid o_t)$ by supervised learning on expert observation–action pairs. This lecture removes the expert. To do that we need a formalism that says what the policy should do without demonstration data — and that formalism starts with the vocabulary from lecture 2: the state $s_t$ , the observation $o_t$ , and the action $a_t$ . The state satisfies the Markov property — $s_{t+1}$ is independent of $s_{t-1}$ given $s_t$ — and this is “the main thing that distinguishes the state from the observation”: the observation is a stochastic function of the state that may or may not contain enough information to recover it. The course covers both the fully observed case, $\pi_\theta(a_t \mid s_t)$ , and the partially observed case, $\pi_\theta(a_t \mid o_t)$ ; Levine admits he will “get a little sloppy” and write $s_t$ where $o_t$ would also work, flagging the cases where the distinction matters.

In place of data, the objective is defined by a reward function $r(s_t, a_t)$ — a scalar function of state and action that “tells us which states and actions are better”. Driving fast down the road: high reward. Collided with another car: low reward. The crucial subtlety is that RL is not about taking high-reward actions now; driving a little too fast is rewarding right up until the inevitable collision. Choosing actions now to receive high rewards later is the decision-making problem at the heart of RL — “by the time you’re about to hit someone, it’s too late.”

Markov chains, MDPs, and POMDPs

The formal objects are built up in three steps. A Markov chain $\mathcal{M} = \{\mathcal{S}, \mathcal{T}\}$ — named for Andrei Markov, who pioneered the study of stochastic processes — has only states and transitions: a state space $\mathcal{S}$ (discrete or continuous) and $\mathcal{T}$ , the transition probability $p(s_{t+1} \mid s_t)$ . It is called a transition operator because of a piece of linear algebra that will matter later: stack the state probabilities at time $t$ into a vector $\mu_t$ with entries $\mu_{t,i} = p(s_t = i)$ , let $\mathcal{T}_{i,j} = p(s_{t+1} = i \mid s_t = j)$ , and the chain rule of probability becomes a matrix–vector product:

$\mu_{t+1} = \mathcal{T} \mu_t$

Definition — Markov decision process

An MDP $\mathcal{M} = \{\mathcal{S}, \mathcal{A}, \mathcal{T}, r\}$ — a 1950s invention associated with Richard Bellman — augments the Markov chain with an action space $\mathcal{A}$ and a reward function $r : \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$ . Transitions now condition on actions, $p(s_{t+1} \mid s_t, a_t)$ , so $\mathcal{T}$ becomes a three-index tensor $\mathcal{T}_{i,j,k} = p(s_{t+1} = i \mid s_t = j, a_t = k)$ — but it is still a linear operator carrying current state and action probabilities to next-state probabilities. A partially observed MDP (POMDP) adds two more objects: an observation space $\mathcal{O}$ and an emission probability $\mathcal{E}$ , i.e. $p(o_t \mid s_t)$ . Rewards are still functions of the true state and action, but the policy must act from observations alone.

The objective: an expectation under the trajectory distribution

Running a policy in an MDP induces a distribution over trajectories $\tau = (s_1, a_1, \ldots, s_T, a_T)$ . By the chain rule — using the Markov property to drop dependence on earlier states — it factorizes into objects we have already defined:

$p_\theta(\tau) = p(s_1) \prod_{t=1}^{T} \pi_\theta(a_t \mid s_t)\, p(s_{t+1} \mid s_t, a_t)$

The RL objective, in its most basic finite-horizon form, is to find

$\theta^\star = \arg\max_\theta\; \mathbb{E}_{\tau \sim p_\theta(\tau)}\!\left[\sum_t r(s_t, a_t)\right] = \arg\max_\theta J(\theta)$

Levine asks you to genuinely stop and internalize this line — the trajectory distribution, how $\theta$ shapes it, what the expected sum of rewards means — because everything in the next several lectures builds on it.

A useful rewriting: group $(s_t, a_t)$ into an augmented state. These augmented states form a Markov chain with transition operator $p\big((s_{t+1}, a_{t+1}) \mid (s_t, a_t)\big) = p(s_{t+1} \mid s_t, a_t)\, \pi_\theta(a_{t+1} \mid s_{t+1})$ — the MDP dynamics times the policy. By linearity of expectation the objective becomes a sum over per-time-step state–action marginals:

$J(\theta) = \sum_{t=1}^{T} \mathbb{E}_{(s_t, a_t) \sim p_\theta(s_t, a_t)}\left[r(s_t, a_t)\right]$

This looks like a useless rewriting; it is what makes the infinite horizon tractable.

The infinite-horizon objective and the stationary distribution

As $T \rightarrow \infty$ the raw sum can diverge, so divide by $T$ (the average-reward formulation; discounting comes later). In the augmented chain, $\mu_t = \mathcal{T}^{\,t-1} \mu_1$ , and one can ask whether $p(s_t, a_t)$ converges to a stationary distribution — the same before and after a transition, $\mu = \mathcal{T}\mu$ , equivalently $(\mathcal{T} - \mathbf{I})\mu = 0$ : $\mu$ is an eigenvector of $\mathcal{T}$ with eigenvalue $1$ . Under two technical conditions — ergodicity (every state reachable from every other with nonzero probability, so where you start eventually stops mattering) and aperiodicity — it always exists. Then all but finitely many terms of the average sit arbitrarily close to $\mu$ , so

$\lim_{T \to \infty} \frac{1}{T} \sum_{t=1}^{T} \mathbb{E}_{(s_t,a_t) \sim p_\theta}\left[r(s_t, a_t)\right] = \mathbb{E}_{(s,a) \sim \mu}\left[r(s, a)\right]$

RL algorithms rarely solve for $\mu$ directly, but manipulating the objective with this linear algebra is central to understanding RL theoretically.

One last observation closes the section: “reinforcement learning is really about optimizing expectations.”

The anatomy of an RL algorithm

Nearly every algorithm in this course shares one high-level skeleton, drawn as three boxes in a loop. The orange box generates samples: run the policy in the environment and collect trajectories — the “trial” in trial-and-error. The green box fits a model or estimates the return — anything that evaluates how the current policy is doing. The blue box improves the policy. Then repeat.

Two instantiations show the range. A policy gradient method makes the green box trivial — sum the rewards of each rollout, $J(\theta) \approx \frac{1}{N} \sum_i \sum_t r_t^i$ — and the blue box a gradient step $\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)$ , nudging good trajectories up and bad ones down. An “RL by backprop” method instead spends the green box training a whole neural network $f_\phi$ so that $s_{t+1} \approx f_\phi(s_t, a_t)$ , then in the blue box backpropagates through $f_\phi$ and $r$ to train the policy.

Which boxes are expensive depends entirely on the setting. If samples come from a real robot, car, or power grid, the orange box runs at “1x real time, until we invent time travel”; the MuJoCo simulator from homework 1 runs up to 10,000x real time, making it trivially cheap. The green box spans a millisecond of summation to hours of model training; the blue box spans one gradient step to backprop-through-a-model. A Q-learning method spends nearly all its effort in the green box — its blue box is just an argmax.

Value functions and Q-functions

Expand the objective’s expectation with the chain rule and it becomes a nest: an expectation over $s_1 \sim p(s_1)$ , inside it one over $a_1 \sim \pi(a_1 \mid s_1)$ , then $r(s_1, a_1)$ plus an expectation over $s_2$ , over $a_2$ , and so on. Messy — unless you had a symbol for everything inside the second bracket. Call it $Q(s_1, a_1)$ , and the whole objective collapses to $\mathbb{E}_{s_1 \sim p(s_1)}\big[\mathbb{E}_{a_1 \sim \pi(a_1 \mid s_1)}[Q(s_1, a_1)]\big]$ . And if you knew $Q(s_1, a_1)$ , improving the policy at the first step would be easy: test each action, put probability $1$ on the argmax.

Definition — Q-function and value function

For a policy $\pi$ , the Q-function at any time step is the expected total reward from taking $a_t$ in $s_t$ and following $\pi$ thereafter:

$Q^\pi(s_t, a_t) = \sum_{t'=t}^{T} \mathbb{E}_{\pi_\theta}\left[r(s_{t'}, a_{t'}) \mid s_t, a_t\right]$

The value function conditions on the state alone — $V^\pi(s_t) = \sum_{t'=t}^{T} \mathbb{E}_{\pi_\theta}\left[r(s_{t'}, a_{t'}) \mid s_t\right]$ — and the two are linked by $V^\pi(s_t) = \mathbb{E}_{a_t \sim \pi(a_t \mid s_t)}\left[Q^\pi(s_t, a_t)\right]$ . The expectation of the value function at the first state, $\mathbb{E}_{s_1 \sim p(s_1)}[V^\pi(s_1)]$ , is the RL objective.

In the anatomy, value functions and Q-functions live in the green box — they are objects that evaluate how good the current policy is — and get used in the blue box to improve it.

The algorithm zoo and its trade-offs

The course’s whirlwind tour sorts algorithms by what they estimate. Policy gradients directly differentiate $J(\theta)$ and ascend. Value-based methods estimate the value function or Q-function of the optimal policy, often with no explicit policy at all — the policy is implicitly $\arg\max_a Q(s,a)$ . Actor-critic methods are the hybrid: fit a value function or Q-function of the current policy, then use it to compute a better policy gradient. Model-based methods estimate the transition model, then use it in one of several ways: plan directly through it (Monte Carlo tree search for chess-like problems, trajectory optimization for continuous control), backpropagate gradients into the policy (simple in principle, needing “quite a few tricks” for numerical stability), learn a value function by dynamic programming, or generate synthetic data for a model-free learner. Named examples the course will cover: Q-learning and DQN, fitted value iteration, REINFORCE, natural policy gradient, TRPO/PPO, A3C, soft actor-critic, Dyna-style methods, guided policy search.

Why so many? Because the trade-offs cut differently per problem. Sample efficiency — how many environment samples until a good policy — hinges on one question above all: is the algorithm off-policy (can improve the policy using previously collected samples) or on-policy (must throw everything away each time the policy changes “even a little bit”)? The rough spectrum from fewer samples to more: model-based deep RL, off-policy Q-learning, actor-critic, on-policy policy gradients, evolutionary and gradient-free methods. But wall clock is not sample efficiency — with a cheap simulator, the right end of the spectrum is often computationally faster, which is exactly why you might choose a less efficient algorithm.

Stability and ease of use ask: does it converge, to what, and every time? Coming from supervised learning you might wonder why this is even a question — the answer is that RL is often not gradient descent. “Convergent algorithms are actually a rare luxury.” Q-learning is a fixed-point iteration whose convergence with neural networks is an open problem; value function fitting at best minimizes Bellman error — which is not the same as achieving reward — and at worst optimizes nothing and may diverge. Model-based RL converges as model fitting, but a better model is not guaranteed to mean a better policy. Policy gradient is the only one that performs true gradient ascent on the objective — and it is the least sample-efficient of the bunch.

Assumptions differ too: full observability (typical for value-fitting methods, mitigated with recurrence and memory), episodic resets (assumed by pure policy gradient methods, favored by the rest), and continuity or smoothness (common in model-based methods derived from optimal control). The lecture closes with worked examples spanning the zoo: Atari from pixels with convolutional Q-learning (Mnih et al. 2013), robotic visuomotor skills with model-based guided policy search, a humanoid learning to walk with a TRPO-family actor-critic, and the grasping robot from lecture 1 — also Q-learning, adapted to continuous actions.

Back of the chalk tray — what to remember

The MDP $\{\mathcal{S}, \mathcal{A}, \mathcal{T}, r\}$ formalizes decision making; the Markov property separates states from observations, and POMDPs add an observation space and emission probabilities.
The RL objective is $\mathbb{E}_{\tau \sim p_\theta(\tau)}[\sum_t r(s_t, a_t)]$ ; grouping $(s_t, a_t)$ into an augmented Markov chain rewrites it over state–action marginals and, via the stationary distribution (eigenvector of $\mathcal{T}$ with eigenvalue 1), extends it to infinite horizon.
Expectations of discontinuous rewards under smooth policy distributions are smooth in the policy parameters — this is why gradient-based RL works on sparse and binary rewards.
Every RL algorithm loops three boxes — generate samples, fit a model / estimate the return, improve the policy — and algorithms differ in where the effort lands.
$Q^\pi$ and $V^\pi$ evaluate a policy; argmaxing $Q^\pi$ improves any policy, and $Q^\pi(s,a) > V^\pi(s)$ flags better-than-average actions — the seeds of Q-learning and actor-critic respectively.
Algorithm choice is trade-offs: on-policy vs off-policy sample efficiency, wall-clock cost, convergence guarantees (rare in RL), and assumptions like full observability, episodic resets, and smoothness.

Check yourself

Conceptual and computational exercises in the lecture’s spirit — work them on paper.

Problem 4.1 stationary distribution computation

A two-state augmented Markov chain has transition operator

$\mathcal{T} = \begin{pmatrix} 0.9 & 0.5 \\ 0.1 & 0.5 \end{pmatrix}$

(column $j$ gives the probabilities of landing in each state from state $j$ ). Verify the chain is ergodic and aperiodic, find the stationary distribution $\mu$ , and compute the infinite-horizon average reward if $r$ assigns $2$ to state 1 and $-4$ to state 2.

Show solution

Every entry of $\mathcal{T}$ is positive, so every state reaches every other with nonzero probability in one step (ergodic) and self-transitions exist (aperiodic) — the stationary distribution exists. Solve $\mu = \mathcal{T}\mu$ with $\mu_1 + \mu_2 = 1$ : the first row gives $\mu_1 = 0.9\mu_1 + 0.5\mu_2$ , so $0.1\mu_1 = 0.5\mu_2$ , i.e. $\mu_1 = 5\mu_2$ . With the normalization, $\mu = (5/6,\, 1/6)$ — an eigenvector of $\mathcal{T}$ with eigenvalue 1, as the theorem requires. The average reward is $\mathbb{E}_\mu[r] = \tfrac{5}{6}(2) + \tfrac{1}{6}(-4) = \tfrac{10 - 4}{6} = 1$ . Note this is exactly $\lim_{T\to\infty} \frac{1}{T}\sum_t \mathbb{E}[r]$ : the finitely many early terms before the marginals converge to $\mu$ are washed out by the $1/T$ factor.

Problem 4.2 smoothness of expectations

A robot attempts a grasp: reward $+1$ if the grasp succeeds, $0$ if it fails — a discontinuous function of the gripper pose. Suppose the policy succeeds with probability $\sigma(\theta) = 1/(1 + e^{-\theta})$ for a scalar parameter $\theta$ . Show that the expected reward is smooth in $\theta$ , compute its derivative, and explain why this does not contradict the reward being non-differentiable.

Show solution

$\mathbb{E}_{\pi_\theta}[r] = 1 \cdot \sigma(\theta) + 0 \cdot (1 - \sigma(\theta)) = \sigma(\theta)$ , which is infinitely differentiable, with $\frac{d}{d\theta}\mathbb{E}[r] = \sigma(\theta)(1 - \sigma(\theta)) > 0$ everywhere — gradient ascent always pushes toward higher success probability. There is no contradiction because differentiation is with respect to the distribution’s parameters, not the outcome variable: the expectation integrates the discontinuous $r$ against a density (here a probability mass) that varies smoothly with $\theta$ . This is the lecture’s mountain-road example in miniature, and the reason RL can optimize sparse or binary rewards with smooth optimization methods.

Problem 4.3 Q, V, and policy improvement

In some state $s$ there are three actions with $Q^\pi(s, a_1) = 4$ , $Q^\pi(s, a_2) = 1$ , $Q^\pi(s, a_3) = -2$ under a uniform policy $\pi(a_i \mid s) = 1/3$ . (a) Compute $V^\pi(s)$ . (b) Which actions are “better than average”? (c) Write the improved policy $\pi'$ from Idea 1 and argue, using the definition of $Q^\pi$ , why it does at least as well as $\pi$ from $s$ .

Show solution

(a) $V^\pi(s) = \mathbb{E}_{a \sim \pi}[Q^\pi(s,a)] = \tfrac{1}{3}(4 + 1 - 2) = 1$ . (b) Better than average means $Q^\pi(s, a) > V^\pi(s) = 1$ : only $a_1$ qualifies ( $4 > 1$ ); $a_2$ is exactly average and $a_3$ is worse. Idea 2 would increase $\pi(a_1 \mid s)$ . (c) $\pi'(a_1 \mid s) = 1$ , zero elsewhere. $Q^\pi(s, a)$ is the expected return from taking $a$ in $s$ and then following $\pi$ — so a single decision at $s$ switched to $a_1$ , with $\pi$ run afterwards, yields expected return $Q^\pi(s, a_1) = 4 \ge V^\pi(s) = 1$ , the return of following $\pi$ throughout. The first step of $\pi'$ can only match or beat $\pi$ ‘s average, whatever $\pi$ is; making this argument at every state and time step (and iterating it) is the policy iteration idea developed later in the course.

Problem 4.4 anatomy and trade-offs

For each algorithm, state what its green box and blue box do, whether it is on-policy or off-policy in its basic form, and one situation where you would prefer it: (a) a policy gradient method, (b) Q-learning, (c) model-based RL with planning.

Show solution

(a) Green box: sum rewards along sampled trajectories — trivially cheap. Blue box: gradient ascent step $\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)$ . On-policy — every step changes the policy, invalidating old samples. Prefer it when samples are cheap (fast simulator) and you want the only method that is true gradient ascent on the actual objective. (b) Green box: fit $Q(s, a)$ — nearly all the effort lives here. Blue box: just $\arg\max_a Q(s, a)$ ; no explicit policy network needed. Off-policy — it can improve from previously collected samples. Prefer it with discrete actions and expensive samples. (c) Green box: fit $p(s_{t+1} \mid s_t, a_t)$ by supervised learning — potentially a large training run per iteration. Blue box: plan through the model (e.g. Monte Carlo tree search, or trajectory optimization in continuous spaces) — possibly with no policy at all. Off-policy and typically the most sample-efficient end of the spectrum, but with the caveat that the model minimizes prediction error, and a better model is not guaranteed to yield a better policy. Prefer it when real-world samples are the binding cost and the dynamics are learnable (often assuming smoothness).