We keep states, actions, rewards and policies. Sampled targets replace model expectations; prediction error and exploration now affect learning.

Bring: The Bellman backup and policy/value distinction from Lecture 7.

We no longer query a model. We act, and a stream comes back:

• the agent chooses $a_t = \pi(s_t)$ — decision,
• the environment returns $r_{t+1}, s_{t+1}$ — the only window onto $P,R$,
• from this stream we must recover $Q^*$ and act on it — learning.

The definition has not changed since Lecture 7 — only our access to it:

The same value, written two ways. Each writing is a recipe for estimating it from samples:

• Monte Carlo reads the left form: wait for the episode to end, average the realized return $G_t$.
• Temporal Difference reads the right form: take one step, then trust your own current estimate of the rest.

Visit $s_t$, watch the episode finish, collect the realized return $G_t = r_{t+1}+\gamma r_{t+2}+\cdots+\gamma^{T-t-1}r_T$. Then nudge:

• Unbiased. $\E[G_t] = V^\pi(s_t)$ exactly — the target is the real thing, not a guess.
• No model, no bootstrap. Each state's estimate stands alone; we never lean on neighbors.
• The price: must wait for the terminal state (no online updates), and the return of a long episode is a high-variance single draw — one unlucky tail corrupts the estimate.

Consider an illustrative episode $A\to B\to A\to\text{terminal}$ with rewards $1,2,3$ and $\gamma=1$. The two returns observed after visiting A are 6 and 3.

Across episodes, keep the count of included visits and update the running average. Neither estimate from this single episode is guaranteed to equal the true value.

Don't wait. After a single transition $(s_t, r_{t+1}, s_{t+1})$, update:

The target contains $V(s_{t+1})$ — our own current estimate. It need not be better on every individual transition. This is bootstrapping.

Let $V(s)=2$, $V(s')=3$, $\alpha=0.2$, and $\gamma=0.9$. We observe reward 1; the next transition pays 4 and ends the episode.

If the first transition had terminated, both targets would be 1: terminal continuation value is zero.

Three ways to back up a value; TD is the one that takes from both parents.

Lecture 7's improvement step, written out:

To turn a value into an action, you must look one step ahead — and looking ahead needs the model.

The Lecture 7 dance is unchanged — evaluate, improve, repeat — but each half is now sampled.

The simplest way to keep trying everything:

1. Generate a complete episode using the current exploratory policy.
2. Work backwards to compute $G_t=r_{t+1}+\gamma G_{t+1}$.
3. Average the selected returns for each visited $(s_t,a_t)$ into $Q(s_t,a_t)$.
4. Make the policy $\varepsilon$-greedy with respect to the updated Q values.

For four actions and $\varepsilon=0.2$, a unique greedy action gets probability 0.85 and each other action gets 0.05.

Put TD evaluation of $Q$ together with $\varepsilon$-greedy improvement. Two natural updates appear, differing in one term:

Let $Q(s,a)=2$, reward $r=1$, $\gamma=0.9$, and $\alpha=0.2$. At the next state, the two action values are 5 and 1. Exploration actually selects the action worth 1.

Cross the two forks of the whole lecture — bootstrap? and whose policy?

Look at what each update assumes about the next step.

• SARSA's target uses $Q(s',a')$ where $a' \sim \pi_{\text{behavior}}$ — the real next action, exploration and all. It is honest about the policy it runs.
• Q-learning's target uses $\max_{a'} Q(s',a')$ — it pretends the next action will be greedy, regardless of the $a'$ actually taken. The behavioral $a'$ is collected, then ignored.

The model probabilities from Lecture 7 are now unavailable to the learner. Observe a heating transition from $x=-2$ to $x'=-1$, with reward −2. Let $Q(-2,\mathrm{heat})=-4$, $\max_aQ(-1,a)=-1$, $\gamma=0.9$ and step size 0.5.

Predict: Should this observation raise or lower the old estimate −4?

Start again from Q = −4. This time the next state remains −2, the measured reward is −5 and its next maximum Q is −3. Keep γ = 0.9 and step size 0.5. Calculate the update.

Those conventions define different MDPs. They must not share the same claimed converged Q table.

With terminal F, the best D → B → F continuation has $Q^*(D,B)=80$, and C → D → B → F has $Q^*(C,D)=64$. These are limits, unlike the intermediate values 50, 20 and 75 on the previous slide.

Everything so far stores one number per $(s,a)$. Then comes Atari:

more configurations than atoms in the universe. A $Q$-table is impossible three times over: too many states to visit, too many to store, and — fatally — no generalization: a table says nothing about a state it has never seen.

Two situations can have the same current image but require different actions:

A single frame at position 20 cannot distinguish them. DQN's input stacks four recent 84 × 84 grayscale frames, and a convolutional network extracts spatial features from that stack.

Treat the Bellman target as a label and minimize squared error on each transition:

with TD error $\delta = r + \gamma \max_{a'} \hat Q(s',a';w) - \hat Q(s,a;w)$.

These three ingredients together create an important source of instability. Their absence is not a universal safety guarantee for arbitrary algorithms or step sizes.

Keep Q-learning's update. Add two stabilizers.

• Experience replay. Store transitions $(s,a,r,s')$ in a buffer $D$; train on random minibatches from it. This reduces temporal correlation within minibatches and reuses experience; the finite replay data are not independent samples from a fixed environment distribution.
• Target network. Compute the target with a frozen copy $w^-$, synced to $w$ only every $C$ steps:

For each stored transition, the target is fixed between target-network updates. This helps stability but does not restore a general convergence guarantee.

For one stored nonterminal transition, let $r=1$, $\gamma=0.9$, and the target network's next values be 5 and 1. The label is $y=1+0.9(5)=5.5$.

If the current network predicts 2:

The derivative with respect to that prediction is $2-5.5=-3.5$, so gradient descent pushes the prediction upward. Do not differentiate through the label.

At the next state, suppose the two networks give:

For immediate reward 1 and discount 0.9:

Double DQN selects $a^*=\argmax_a Q_w(s',a)=A$, then evaluates that action with the target network:

The two tricks opened a decade of refinements, each patching a named flaw:

• Double DQN — the $\max$ over-estimates; decouple action-selection from evaluation. (van Hasselt et al., 2016)
• Dueling networks — split $\hat Q$ into state-value $+$ advantage; learn "which states matter" separately. (Wang et al., 2016)
• Prioritized replay — sample high-error transitions more often. (Schaul et al., 2016)
• Rainbow — combine them; the combination improved the reported Atari benchmark results. (Hessel et al., 2018)

Both estimate $V^\pi(s)=\E_\pi[G_t\mid s_t=s]$ from samples; they differ in what they sample.

Claim (Watkins & Dayan, 1992): in a finite stationary MDP with bounded rewards and $0\le\gamma<1$, tabular Q-learning converges to $Q^*$ with probability 1, provided

• every state–action pair $(s,a)$ is visited infinitely often (the role of exploration, e.g. $\varepsilon>0$), and
• for each state–action pair, its update step sizes satisfy the Robbins–Monro conditions $\sum_t \alpha_t = \infty$, $\sum_t \alpha_t^2 < \infty$.

Why it holds (sketch). The Bellman optimality operator $(\mathcal{T}Q)(s,a) = \E_{s'}[\,r + \gamma\max_{a'}Q(s',a')\,]$ is a $\gamma$-contraction in the sup-norm, so it has a unique fixed point $Q^*$. The Q-learning update is a stochastic approximation of $\mathcal{T}$: each step replaces the expectation by one sample. Robbins–Monro step sizes average out the sampling noise; infinite visitation guarantees every entry keeps being corrected. Together they drive $Q \to Q^*$.

What breaks under approximation. Replace the table by $\hat Q(\cdot;w)$ and the update is no longer a contraction in any norm the parameters respect — the projection onto the function class can expand distances. That is the formal root of the deadly triad, and the reason DQN needs its two crutches.

Linear case $\hat Q(s,a;w) = w^\top \phi(s,a) = \sum_k w_k \phi_k(s,a)$. Per-transition squared TD error:

Differentiate, holding the target fixed (semi-gradient):

In vector form $w \leftarrow w + \alpha\,\delta\,\phi(s,a)$ — the tabular update is the special case $\phi(s,a)=\mathbf{e}_{(s,a)}$ (a one-hot indicator), which is why tabular RL is "just" function approximation with the most local possible features. For a neural net, $\phi$ becomes $\nabla_w \hat Q(s,a;w)$ and the same line holds.

The branch we acknowledged in Act 0 and walked away from. Estimate the model from the same stream of experience:

Then solve the estimated MDP with any Lecture 7 method (value / policy iteration).

• Pro — sample efficiency: a learned model can be "replayed" indefinitely; each real transition informs the value of many states through planning.
• Con — model bias: errors in $\hat P,\hat R$ compound through planning; you optimize for a world that is slightly wrong.
• Con — cost: estimating a full kernel is far more than estimating the $Q^*$ we actually act on.

This is why model-free dominated the deep-RL era — and why Lecture 11 returns to model-based methods only once it can make the learned model carry its weight (planning, Dyna, differentiable control).

Every object of Lecture 7 has a sampled counterpart. Keep this in sight.

The most literal idea: estimate $P,R$ from data, then run Lecture 7.

Plug in, solve the MDP. This is model-based RL, and it is perfectly valid.