Lecture 07 · Part 2

Value Function Methods

What if we drop the actor entirely? Levine shows that an arg max over the advantage is itself a policy — at least as good as whatever policy produced the advantage — and builds the whole value-based family from it: policy iteration, value iteration, fitted Q iteration, and online Q-learning. The lecture ends with the honest theory: with neural networks these methods are not gradient descent and are not guaranteed to converge, because a Bellman backup followed by a projection is not a contraction.

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

Can we skip learning a policy entirely?

Actor-critic, as covered last lecture, still carries a policy network: sample from the current policy, fit a value function $V^\pi_\phi(s)$ , form advantage estimates $\hat{A}^\pi(s_i, a_i) = r(s_i, a_i) + \gamma V^\pi_\phi(s_i') - V^\pi_\phi(s_i)$ , and push them through the policy gradient. The question that opens this lecture: “can we maybe omit the policy gradient entirely?” The value function already tells us which states are better than which other states — so just select the actions that lead to the better states.

The formal version runs through the advantage. $A^\pi(s_t, a_t) = Q^\pi(s_t, a_t) - V^\pi(s_t)$ measures how much better $a_t$ is than the average action the policy would have taken. Then $\arg\max_{a_t} A^\pi(s_t, a_t)$ is the best action available from $s_t$ if you follow $\pi$ thereafter.

The arg max policy improves on any policy

Define a new, implicit policy

$\pi'(a_t \mid s_t) = \begin{cases} 1 & \text{if } a_t = \arg\max_{a_t} A^\pi(s_t, a_t) \\ 0 & \text{otherwise} \end{cases}$

Because the arg max action is the best action from $s_t$ under $\pi$ ‘s subsequent behavior, it is at least as good as any action $\pi$ itself would have sampled — “and the interesting thing is that this is true regardless of what $\pi$ actually is.” Even a terrible random policy improves under this construction. No second network is needed: the policy is represented implicitly by the arg max, and the only thing left to learn is the value function.

This slots into the usual three-box anatomy with one box gutted: the orange box still generates samples and the green box fits $Q^\pi$ or $V^\pi$ , but the blue box no longer does any learning — it just sets the policy to the arg max. Alternating the two steps — evaluate $A^\pi$ , then set $\pi \leftarrow \pi'$ — is policy iteration. Step two is trivial with discrete actions (check every action’s advantage); continuous actions wait for the next lecture. The whole puzzle is step one: how do you evaluate $A^\pi(s, a) = r(s, a) + \gamma \mathbb{E}[V^\pi(s')] - V^\pi(s)$ ? It suffices to evaluate $V^\pi$ .

Dynamic programming when you know everything

Suspend the model-free setting for a moment: assume known transition probabilities $p(s' \mid s, a)$ and state and action spaces small enough to enumerate — a grid world with 16 states and 4 actions is the mental picture. Then $V^\pi$ is literally a table of 16 numbers and the transitions are a $16 \times 16 \times 4$ tensor; this is what “tabular RL” means. The bootstrapped update from lecture 6 can now be computed exactly, expectations and all:

$V^\pi(s) \leftarrow \mathbb{E}_{a \sim \pi(a \mid s)}\!\left[r(s, a) + \gamma\, \mathbb{E}_{s' \sim p(s' \mid s, a)}[V^\pi(s')]\right]$

using the current table entry for $V^\pi(s')$ . And since the arg max policy is deterministic, the outer expectation collapses:

$V^\pi(s) \leftarrow r(s, \pi(s)) + \gamma\, \mathbb{E}_{s' \sim p(s' \mid s, \pi(s))}[V^\pi(s')]$

Repeating this recursion is policy evaluation; it provably converges to a fixed point, which is the true $V^\pi$ . (Levine’s aside for the mathematically inclined: the fixed-point condition is a system of linear equations in the table entries, solvable directly with any linear solver — “a good exercise to make sure that you really understand dynamic programming.”)

Policy iteration can then be short-circuited. Since subtracting $V^\pi(s)$ — a term that doesn’t depend on the action — can’t change an arg max over actions, $\arg\max_a A^\pi(s, a) = \arg\max_a Q^\pi(s, a)$ . Picture the Q-function as a table with a row per state and a column per action: the arg max finds the biggest entry in each row (the policy), and evaluating that policy just plugs the index back in to read off the same entry (the value). So skip the indices and take the values directly. That is value iteration:

$\text{1. } Q(s, a) \leftarrow r(s, a) + \gamma\, \mathbb{E}[V(s')] \qquad \text{2. } V(s) \leftarrow \max_a Q(s, a)$

No explicit policy ever appears — it lives implicitly inside the max. Plug step two into step one and you don’t even need to store $V$ : only the Q-table remains.

Neural networks and fitted value iteration

Why not always use a table?

So represent $V_\phi : \mathcal{S} \rightarrow \mathbb{R}$ with a neural network and fit it the way lecture 6 fit the critic — least-squares regression onto target values. Using the value-iteration targets gives fitted value iteration:

$\text{1. } y_i \leftarrow \max_{a_i}\left(r(s_i, a_i) + \gamma\, \mathbb{E}[V_\phi(s_i')]\right) \qquad \text{2. } \phi \leftarrow \arg\min_\phi \frac{1}{2} \sum_i \left\lVert V_\phi(s_i) - y_i \right\rVert^2$

A reasonable algorithm — but step one still requires the dynamics, in two ways: the expectation over $s'$ , and, “perhaps more importantly,” evaluating the max requires trying every action from the same state, which you cannot do by running policies in the world unless you can teleport back to a state and try again.

Trading V for Q makes it model-free

Return to policy iteration and write the policy-evaluation recurrence for the Q-function instead of the value function:

$Q^\pi(s, a) \leftarrow r(s, a) + \gamma\, \mathbb{E}_{s' \sim p(s' \mid s, a)}\left[Q^\pi(s', \pi(s'))\right]$

The change looks cosmetic but is “a very very important one”: the distribution being sampled is conditioned on the $(s, a)$ tuple you already have, so as $\pi$ changes, the samples you need do not. The policy appears in exactly one place — as an argument to the Q-function at $s'$ — not in the simulator. Any bucket of $(s, a, s')$ transitions, collected by any policy, can fit $Q^\pi$ for every $\pi$ . “This is the basis of most value-based model-free RL algorithms.”

Applying the max trick to this recurrence gives the workhorse of the lecture.

Code walkthrough — Full fitted Q-iteration

Three steps, each with a free parameter you must choose:

# hyperparameters: dataset size N, collection policy, inner iterations K, gradient steps S
while True:
    # 1. collect N transitions (s_i, a_i, s'_i, r_i) using some policy (any policy!)
    for k in range(K):                      # 2-3 alternate K times per data collection
        # 2. compute targets with the previous Q-function:
        #    y_i = r(s_i, a_i) + gamma * max_a' Q_phi(s'_i, a')
        # 3. fit a new phi with S gradient steps on:
        #    argmin_phi 1/2 * sum_i || Q_phi(s_i, a_i) - y_i ||^2

The expectation over $s'$ is replaced by the single sampled $s_i'$ , and $\mathbb{E}[V(s_i')]$ is approximated by $\max_{a'} Q_\phi(s_i', a')$ — so the max is over actions at the next state inside the network, requiring no simulation of alternative actions. Pluses: works on off-policy samples; only one network, no high-variance policy gradient. Minus: no convergence guarantees with neural networks. A common architecture for discrete actions outputs one Q-value per action from a state input — a special case of the state-action-input design.

What is this optimizing? Step three minimizes the Bellman error — the squared difference between $Q_\phi(s, a)$ and the targets. If that error is driven to zero, then $Q_\phi(s, a) = r(s, a) + \gamma \max_{a'} Q_\phi(s', a')$ , which is an optimal Q-function corresponding to the optimal policy. In the tabular case the error does go to zero and you recover $Q^\star$ . If it is not zero, “most guarantees are lost when we leave the tabular case.”

Online Q-learning and exploration

Set the hyperparameters to their smallest values — one transition, one target, one gradient step — and fitted Q iteration becomes classic online Q-learning (Watkins): take an action, observe $(s_i, a_i, s_i', r_i)$ , compute $y_i = r(s_i, a_i) + \gamma \max_{a'} Q_\phi(s_i', a')$ , then

$\phi \leftarrow \phi - \alpha \frac{dQ_\phi}{d\phi}(s_i, a_i)\left(Q_\phi(s_i, a_i) - y_i\right)$

where the parenthesized quantity is the temporal difference error. It is off-policy: the action in step one need not come from the latest greedy policy. And it had better not, at least not exactly. The greedy arg max policy is deterministic, and if the initial Q-function is bad — not random, arbitrary — it will commit to the same poor action every time it enters a state, potentially “in perpetuity,” never discovering that better actions exist. So inject randomness:

Epsilon-greedy: take the greedy action with probability $1 - \epsilon$ , and each other action with probability $\epsilon / (|\mathcal{A}| - 1)$ . Simple, ubiquitous, and what you implement in homework 3; a common refinement anneals $\epsilon$ from large (bad early Q-function) to small (trustworthy late Q-function).
Boltzmann (softmax) exploration: $\pi(a_t \mid s_t) \propto \exp(Q_\phi(s_t, a_t))$ . Two advantages over epsilon-greedy: two nearly-equal actions get nearly-equal probability instead of one hogging the greedy mass, and an action already known to be terrible is almost never wasted exploration.

More sophisticated exploration gets its own lectures in the second half of the course.

The sad theory: why none of this converges with neural nets

Does value iteration converge, and to what? Define the Bellman operator on the value table (a vector with one entry per state):

$V^\star$ — the value function of the optimal policy, satisfying $V^\star(s) = \max_a \left[r(s, a) + \gamma \mathbb{E}[V^\star(s')]\right]$ — is a fixed point of $\mathcal{B}$ , and it always exists, is always unique, and always yields the optimal policy through the arg max. So the question is whether the fixed point iteration $V \leftarrow \mathcal{B}V$ reaches it.

Tabular value iteration converges

$\mathcal{B}$ is a contraction in the infinity norm with coefficient $\gamma$ : for any $V, \bar{V}$ , $\lVert \mathcal{B}V - \mathcal{B}\bar{V} \rVert_\infty \le \gamma \lVert V - \bar{V} \rVert_\infty$ . Choosing $\bar{V} = V^\star$ and using $\mathcal{B}V^\star = V^\star$ gives $\lVert \mathcal{B}V - V^\star \rVert_\infty \le \gamma \lVert V - V^\star \rVert_\infty$ — every application shrinks the worst-state disagreement with $V^\star$ by a factor $\gamma$ , so tabular value iteration converges to the optimum. (The contraction proof itself is a standard textbook result.)

Fitted value iteration adds a second operator. Supervised learning searches a hypothesis set $\Omega$ — all neural nets of your architecture — for the element closest to the targets, and since the targets are exactly $\mathcal{B}V$ , step two is a projection: $\Pi V = \arg\min_{V' \in \Omega} \frac{1}{2} \sum \lVert V'(s) - V(s) \rVert^2$ . Fitted value iteration in one line is $V \leftarrow \Pi \mathcal{B} V$ . Geometrically: $\mathcal{B}V$ steps off the manifold of representable functions, and $\Pi$ drops it back down at a right angle, in the $\ell_2$ norm. $\Pi$ is itself a contraction in $\ell_2$ — projecting two points onto a line can only bring them closer.

So: value iteration converges in the tabular case; fitted value iteration does not converge in general — and often doesn’t in practice. The same story holds verbatim for fitted Q iteration ( $\mathcal{Q} \leftarrow \Pi \mathcal{B} \mathcal{Q}$ with the max moved after the transition operator), for online Q-learning, and — a sad corollary — for the actor-critic value fitting of last lecture, which also composes a bootstrap backup with a projection.

One seeming contradiction remains: step three looks like regression, and regression converges — isn’t this just gradient descent? No. “Q-learning is not actually gradient descent”: the target values themselves depend on $Q_\phi$ , but no gradient flows through them, so the update is not the gradient of any well-defined objective. You could differentiate through the targets — the result is the residual algorithm, which is guaranteed to converge but has such poor numerical properties that plain, unguaranteed Q-learning “tends to work much much better” in practice. The next lecture is about making it work.

Back of the chalk tray — what to remember

An arg max over the advantage is itself a policy, at least as good as the policy that produced the advantage — so value-based methods learn only $V$ or $Q$ and represent the policy implicitly.
Policy iteration alternates policy evaluation with the arg max update; the max trick short-circuits it into value iteration, since evaluating the arg max action is just taking the max.
Tables scale exponentially in state dimension (the curse of dimensionality); function approximation replaces the table with regression onto Bellman targets.
Rewriting the recurrence on $Q$ instead of $V$ makes the method model-free and off-policy: the policy appears only as an argument to the Q-function, never in the sampling distribution, so any $(s, a, s')$ transitions work.
Greedy action selection during learning gets stuck; epsilon-greedy and Boltzmann exploration inject the randomness that lets a bad Q-function recover.
$\mathcal{B}$ contracts in the infinity norm and the projection $\Pi$ contracts in $\ell_2$ , but $\Pi\mathcal{B}$ is not a contraction in any norm — fitted value iteration, fitted Q iteration, Q-learning, and bootstrapped critic fitting all lose their convergence guarantees with neural networks, and the update is not the gradient of any well-defined objective.

Check yourself

Derivation and calculation exercises in the lecture’s spirit — work them on paper.

Problem 7.1 policy evaluation as linear algebra

Levine notes that tabular policy evaluation is really a system of linear equations. Take a two-state MDP with a deterministic policy $\pi$ : from $s_1$ the policy’s action moves to $s_2$ with probability 1 and earns reward 0; from $s_2$ it stays in $s_2$ with probability 1 and earns reward 1. With $\gamma = 0.9$ , write the fixed-point equations $V^\pi = r + \gamma T V^\pi$ , solve them exactly, and confirm that repeated application of the bootstrapped update converges to the same answer from $V^\pi = (0, 0)$ .

Show solution

The equations are $V^\pi(s_1) = 0 + \gamma V^\pi(s_2)$ and $V^\pi(s_2) = 1 + \gamma V^\pi(s_2)$ . The second gives $V^\pi(s_2) = 1/(1 - \gamma) = 10$ ; substituting gives $V^\pi(s_1) = 0.9 \times 10 = 9$ . In matrix form this is $(I - \gamma T)V^\pi = r$ with $T = \begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix}$ and $r = (0, 1)^\top$ , solvable by any linear solver. Starting the recursion from $(0,0)$ : after one sweep $(0, 1)$ , then $(0.9, 1.9)$ , then $(1.71, 2.71)$ , …; each sweep adds $\gamma^k$ -scaled corrections, and the iterates converge geometrically to $(9, 10)$ — exactly the contraction-by- $\gamma$ behavior of the Bellman backup, here for a fixed policy.

Problem 7.2 arg max policy improvement

Show that the implicit policy $\pi'(a \mid s)$ that puts probability 1 on $\arg\max_a A^\pi(s, a)$ satisfies $\mathbb{E}_{a \sim \pi'}[A^\pi(s, a)] \ge \mathbb{E}_{a \sim \pi}[A^\pi(s, a)]$ for every state, computing the right-hand side explicitly. Why does the argument make no assumption about the quality of $\pi$ ?

Show solution

First the right-hand side: $\mathbb{E}_{a \sim \pi}[A^\pi(s, a)] = \mathbb{E}_{a \sim \pi}[Q^\pi(s, a)] - V^\pi(s) = V^\pi(s) - V^\pi(s) = 0$ , since $V^\pi$ is by definition the expectation of $Q^\pi$ under the policy’s own action distribution. The left-hand side is $\max_a A^\pi(s, a)$ , and a maximum is always at least the mean: $\max_a A^\pi(s, a) \ge \mathbb{E}_{a \sim \pi}[A^\pi(s, a)] = 0$ . So the greedy action is at least as good, in advantage terms, as the average action $\pi$ takes — with equality only when $\pi$ already concentrates on maximizing actions. Nothing in the chain used any property of $\pi$ beyond the definitions of $Q^\pi$ , $V^\pi$ , and $A^\pi$ ; that is why even an arbitrary random policy improves under the arg max construction, which is the engine of policy iteration.

Problem 7.3 locating the policy dependence

Consider the two policy-evaluation recurrences from the lecture: $V^\pi(s) \leftarrow r(s, \pi(s)) + \gamma\, \mathbb{E}_{s' \sim p(s' \mid s, \pi(s))}[V^\pi(s')]$ and $Q^\pi(s, a) \leftarrow r(s, a) + \gamma\, \mathbb{E}_{s' \sim p(s' \mid s, a)}[Q^\pi(s', \pi(s'))]$ . You have a fixed buffer of transitions $(s_i, a_i, s_i')$ collected by an old policy, and $\pi$ keeps changing as policy iteration proceeds. Which recurrence can you keep fitting from the buffer without collecting new data, and exactly why does the other one fail?

Show solution

The Q recurrence works. Its sampling distribution $p(s' \mid s, a)$ is conditioned on the stored $(s_i, a_i)$ pair, which is fixed data — when $\pi$ changes, the distribution the stored $s_i'$ were drawn from does not change, so the samples remain valid forever. The policy appears only as an argument to the Q-function, $Q^\pi(s_i', \pi(s_i'))$ , which is a network evaluation, not an environment interaction. The V recurrence fails because $\pi$ sits on the right of the conditioning bar: the expectation is over $s' \sim p(s' \mid s, \pi(s))$ , so when the policy changes its action at $s$ , you need next-state samples for the new action — which requires returning to $s$ and trying a different action, impossible without teleportation. This one-symbol difference is why fitted Q iteration is a model-free, off-policy algorithm and is “the basis of most value-based model-free RL algorithms.”

Problem 7.4 exploration rule arithmetic

A state has three actions with current Q-values $Q = (1.0,\, 0.9,\, -5.0)$ . Compute the action probabilities under epsilon-greedy with $\epsilon = 0.1$ and under Boltzmann exploration $\pi(a) \propto \exp(Q(a))$ . Which of Levine’s two arguments for Boltzmann over epsilon-greedy do the numbers illustrate?

Show solution

Epsilon-greedy: the greedy action gets $1 - \epsilon = 0.9$ ; the other two split $\epsilon$ evenly, $\epsilon / (|\mathcal{A}| - 1) = 0.05$ each. So $(0.9, 0.05, 0.05)$ . Boltzmann: $\exp(1.0) \approx 2.718$ , $\exp(0.9) \approx 2.460$ , $\exp(-5.0) \approx 0.0067$ ; the sum is $\approx 5.185$ , giving probabilities $\approx (0.524, 0.474, 0.001)$ . Both of Levine’s arguments appear at once. First, actions 1 and 2 are nearly equally good, and Boltzmann explores them nearly equally ( $0.524$ vs $0.474$ ), while epsilon-greedy gives the marginal winner eighteen times the probability of the runner-up. Second, action 3 is already known to be terrible, and Boltzmann essentially never wastes a sample on it ( $0.1\%$ ), while epsilon-greedy insists on trying it a full $5\%$ of the time.

Problem 7.5 contractions in mismatched norms

$\mathcal{B}$ is a contraction with coefficient $\gamma$ in the infinity norm, and the projection $\Pi$ onto the hypothesis set $\Omega$ is a contraction (coefficient 1) in the $\ell_2$ norm. (a) If both were contractions in the same norm, what could you conclude about fitted value iteration $V \leftarrow \Pi \mathcal{B} V$ ? (b) Explain, via the lecture’s geometric picture, how the composition can nonetheless move $V$ further from $V^\star$ . (c) What does this imply about the actor-critic algorithm of lecture 6?

Show solution

(a) Contraction coefficients compose multiplicatively within a single norm: $\lVert \Pi\mathcal{B}V - \Pi\mathcal{B}\bar{V} \rVert \le 1 \cdot \gamma \lVert V - \bar{V} \rVert$ . The composition would be a $\gamma$ -contraction, would have a unique fixed point, and fitted value iteration would converge to it — the tabular convergence argument would go through. (b) The guarantees live in different geometries. The backup shrinks the largest per-state gap to $V^\star$ ; the projection then moves the point back onto $\Omega$ along the shortest Euclidean path — but “as close as possible in $\ell_2$ ” to $\mathcal{B}V$ can be far from $V^\star$ in either norm. In the lecture’s picture, $\mathcal{B}V$ steps toward the star, off the line representing $\Omega$ , and the right-angle projection lands at a point on the line further from the star than $V$ was; iterating can drift away indefinitely. Neither step ever violates its own contraction property. (c) The critic update in actor-critic is exactly a bootstrap backup followed by an $\ell_2$ regression — the same $\Pi \mathcal{B}$ composition — so fitted bootstrapped policy evaluation inherits the same failure: it is not guaranteed to converge with function approximation either.