Model-Free Prediction and Control

The foundations of reinforcement learning gave us the Bellman equations and the policy-/value-iteration machinery that solves them. Both assume a model: the transition kernel $P(s^{\prime }\mid s,a)$ and the reward function $R(s,a)$ are known, so every backup is an exact expectation over $s^{\prime }$. The agent in this lesson has neither. It sees only a stream of transitions $(S_t,A_t,R_{t+1},S_{t+1})$ drawn by acting in the environment, and must estimate value functions and improve its policy from that stream alone. This is the model-free setting, and it splits into two problems we treat in turn.

The object both methods estimate is the return, the discounted sum of rewards from time $t$ onward, and the value functions are its expectation:

Without a model the expectation cannot be computed, only sampled. Every algorithm below is a different answer to one question: given a stream of experience, how do you estimate ${\mathbb{E}}_{\pi }[G_t]$?

Monte Carlo prediction

The most direct estimator is the one from Monte Carlo methods: $v_{\pi }(s)$ is an expectation, so average sampled returns. Run an episode to termination, compute the realized return $G_t$ from each visited state, and let $V(s)$ be the mean of the returns observed from $s$. No model, no bootstrapping; the estimate is grounded entirely in completed experience.

The distinction matters for the analysis. If a state recurs inside one episode, its two returns share a common tail of rewards, so they are correlated. First-visit MC sidesteps this by keeping only one return per episode: the returns it averages are independent draws of the same random variable $G_t\mid S_t=s$, so the ordinary law of large numbers applies and its estimate is unbiased at every sample size with error shrinking like $1/\sqrt{n}$ in the number of visits $n$. Every-visit MC reuses the correlated within-episode returns; it is biased for finite $n$ but the bias vanishes as $n\to \infty$, and it often wastes less data.

The sample mean is an incremental update

Averaging returns does not require storing every return seen from $s$. The arithmetic mean of $n$ numbers can be written as a correction to the mean of the first $n-1$, which turns a batch average into a constant-memory online rule. Write $V_n(s)$ for the mean of the first $n$ returns $G_1,\dots ,G_n$ observed from $s$. Then

Expand and regroup the last expression around $V_{n-1}$:

The batch average and this one-line update produce the identical number at every $n$; nothing is approximated. Maintaining a visit count $N(s)$, each new return $G_t$ therefore nudges the running estimate toward itself by a $1/N(s)$ fraction of the residual:

The bracketed residual $G_t-V(S_t)$ is a prediction error, and the step size $1/N(s)$ shrinks as evidence accumulates, so early returns move the estimate a lot and later ones barely at all. Replacing $1/N(s)$ with a constant step $\alpha$ gives a running average that tracks a nonstationary target, the form we keep for the rest of the lesson:

A constant $\alpha$ never lets the step size vanish, so this update weights recent returns more heavily than old ones, a geometric recency weighting worth having when the policy (and thus the return distribution) is still changing. The estimator is unbiased in the $1/N$ case because ${\mathbb{E}}_{\pi }[G_t\mid S_t=s]=v_{\pi }(s)$ exactly; MC regresses $V(s)$ directly onto the very quantity it targets, with no model and no bootstrap in between.

Monte Carlo control

Prediction estimates $v_{\pi }$; control must improve $\pi$. Two obstacles appear at once. First, greedy improvement needs action values, not state values: ${\pi }^{\prime }(s)=\arg {\max }_{a}q(s,a)$ requires $q$, since without a model we cannot turn $v$ into a one-step lookahead. So MC control estimates $Q(s,a)$ directly, averaging returns following each state-action pair. Second, a purely greedy policy stops exploring: actions it currently rates poorly are never tried, so their estimates never improve. The standard fix is $\epsilon$-greedy action selection.

The single parameter $\epsilon$ sets the balance between exploitation (act on what you believe is best now) and exploration (try alternatives to correct a wrong belief). Large $\epsilon$ gathers information but earns little reward; $\epsilon =0$ maximizes immediate reward but can lock in a suboptimal action whose true value was never sampled.

$\epsilon$-greedy improvement is sound: any $\epsilon$-greedy policy with respect to $q_{\pi }$ is at least as good as $\pi$ itself.

Interleaving $\epsilon$-greedy evaluation with $\epsilon$-greedy improvement converges, provided exploration decays so that the limiting policy is greedy. That condition has a name.

The structural weakness of MC is that it needs complete episodes. The return $G_t$ is unknown until termination, so MC cannot update mid-episode, cannot learn in continuing (non-terminating) tasks, and waits a long time on long episodes before any signal propagates.

Temporal-difference learning

Temporal-difference learning removes the wait. Instead of substituting the full sampled return $G_t$, it substitutes the one-step bootstrap target$R_{t+1}+\gamma V(S_{t+1})$: one real reward plus the current estimate of the rest. This is the sampled form of the Bellman expectation equation $v_{\pi }(s)={\mathbb{E}}_{\pi }[R_{t+1}+\gamma v_{\pi }(S_{t+1})\mid S_t=s]$.

The TD error appears in every method that follows: it is the gap between what the agent expected and what one step of experience plus its own forecast now suggest. MC and TD differ only in their target: MC regresses $V(S_t)$ toward the realized $G_t$, TD toward $R_{t+1}+\gamma V(S_{t+1})$. Dynamic programming uses the same target as TD but takes a full expectation over $S_{t+1}$ instead of sampling one.

The implications are immediate: TD learns online, after every step, from incomplete episodes, and works in continuing tasks where no terminal state exists. It bootstraps, so it can begin propagating value before any episode finishes.

A worked TD(0) update

For example, take $\gamma =0.9$ and step size $\alpha =0.1$. The current table holds $V(S_t)=5$ and $V(S_{t+1})=8$. The agent takes its action and observes reward $R_{t+1}=2$, landing in $S_{t+1}$. Form the bootstrap target, then the TD error, then the update:

The estimate moves a tenth of the way from $5$ toward the target $9.2$. It did not jump to $9.2$: a single transition is one noisy sample, and $\alpha =0.1$ limits how much weight it receives. Had the reward been unluckily large, the target would overshoot and the next transition from $S_t$ would pull the estimate part of the way back; the step size averages these samples over time. Every method in this lesson is a variation on this three-line loop, changing only what fills the target slot.

Bias and variance

TD and MC are both correct in the limit, but they trade bias against variance. The MC target $G_t$ is an unbiased sample of $v_{\pi }(S_t)$ but accumulates the randomness of every reward and transition along the whole trajectory, so its variance is large. The TD target $R_{t+1}+\gamma V(S_{t+1})$ depends on a single random transition, so its variance is small, but it bootstraps off the current estimate $V$, which is wrong early in training, so it is biased until $V$ converges.

The Markov-property row is the deepest distinction. On finite data, MC converges to the values that minimize mean-squared error on the observed returns, whereas TD(0) converges to the values of the maximum-likelihood Markov model fit to the data, the so-called certainty-equivalence estimate. When the environment really is Markov, TD's structural assumption is a feature and it is typically far more data-efficient; when it is not, MC's model-freedom is safer.

On-policy control: SARSA

Control needs action values, and the same TD idea applied to $Q$ gives SARSA, named for the quintuple $(S_t,A_t,R_{t+1},S_{t+1},A_{t+1})$ that the update consumes. The bootstrap target uses the action $A_{t+1}$ that the agent actually takes next under its current policy.

SARSA is on-policy: the target evaluates the very policy generating the data, so as the policy improves, the values it learns are the values of the improving policy. With a GLIE schedule the policy becomes greedy and SARSA converges to $q_{\star }$.

Off-policy control: Q-learning

Q-learning changes one symbol and the character of the algorithm with it. Its target bootstraps off the greedy action ${\max }_{a^{\prime }}Q(S_{t+1},a^{\prime })$, not the action actually taken. It learns about the optimal policy while behaving by an exploratory one.

This is off-policy: the behavior policy that selects $A_t$ (e.g. $\epsilon$-greedy, for exploration) differs from the target policy the update evaluates (greedy). Because the $\max$ target is a sampled form of the Bellman optimality equation, Q-learning converges to $q_{\star }$ directly under the standard step-size conditions, regardless of the behavior policy, as long as it keeps visiting every pair.

One term separates the two

Line up the two targets and only one factor differs:

SARSA plugs in $Q$ at the action $A_{t+1}$ the behavior policy actually samples next. That action is $\epsilon$-greedy, so with probability $\epsilon$ it is a random, possibly bad action, and its low value is folded into the target. The target therefore describes the value of following the exploratory policy, including its mistakes; SARSA evaluates the policy that generated the data, which is the definition of on-policy. Q-learning replaces $Q(S_{t+1},A_{t+1})$ with ${\max }_{a^{\prime }}Q(S_{t+1},a^{\prime })$, the value of the best action regardless of what the agent will do next. The $\max$ erases the behavior policy from the target: whatever exploratory action gets taken, the bootstrap always assumes greedy continuation. That is why the target policy (greedy) is decoupled from the behavior policy ($\epsilon$-greedy) — the decoupling that defines off-policy learning. When $\epsilon \to 0$ the sampled action and the greedy action coincide and the two updates become identical; the gap between them is the cost of exploration, which SARSA counts and Q-learning ignores.

The on-policy/off-policy gap changes the actual path the agent learns. The canonical demonstration is cliff walking: a gridworld where the bottom edge between start and goal is a cliff that costs $-100$ and resets the agent, while every other step costs $-1$. The optimal path hugs the cliff edge. Q-learning learns exactly that optimal greedy path. SARSA, because it evaluates the $\epsilon$-greedy policy it actually follows, accounts for the random exploratory steps that occasionally push it off the cliff, so it learns a safer path one row away from the edge, earning more reward online during $\epsilon$-greedy training.

n-step returns and the unified spectrum

MC and TD(0) are the endpoints of a dial. TD(0) bootstraps after one reward; MC after all of them. In between, the $n$-step return takes $n$ real rewards and then bootstraps:

At $n=1$ this is the TD(0) target; as $n\to \infty$ (to termination) it is the MC return $G_t$. The corresponding $n$-step TD update is $V(S_t)\leftarrow V(S_t)+\alpha [G_t^{(n)}-V(S_t)]$. Intermediate $n$ typically beats both endpoints: enough real reward to cut the bootstrap bias, few enough steps to hold the variance down.

TD($\lambda$) and eligibility traces

Rather than commit to one $n$, TD($\lambda$) averages all of them. The $\lambda$-return is a geometric average of every $n$-step return, weighted by $(1-\lambda ){\lambda }^{n-1}$:

The weights sum to one. At $\lambda =0$ all weight collapses onto $G_t^{(1)}$, recovering TD(0); at $\lambda =1$ the average reduces to the MC return $G_t$. The single knob $\lambda$ sweeps continuously between bootstrapping and full sampling.

The $\lambda$-return as written is a forward view: it looks ahead to future rewards, so like MC it needs the whole episode. The equivalent backward view makes it online and incremental through eligibility traces. Each state keeps a trace $e(s)$ that spikes on visit and decays by $\gamma \lambda$, marking how recently and how often it was seen. A single TD error ${\delta }_t$ is then broadcast to all states in proportion to their trace.

For an offline (whole-episode) update, the backward and forward views compute exactly the same total change, so eligibility traces are a memory-efficient, causal implementation of the $\lambda$-return rather than a different algorithm.

Function approximation and semi-gradient TD

A table $V(s)$ is impossible when the state space is huge or continuous, the regime every deep RL agent lives in. We replace the table with a parametric $\hat{v}(s;w)\approx v_{\pi }(s)$, a linear map or a neural network with weights $w$, and learn $w$ by stochastic gradient descent. The natural objective is the mean-squared value error, the value gap weighted by how often the policy visits each state:

where $d_{\pi }$ is the on-policy state distribution. The true target $v_{\pi }(s)$ is unknown, so we substitute a sampled target. With the MC target $G_t$ this is honest SGD on a sampled return. With the TD target$R_{t+1}+\gamma \hat{v}(S_{t+1};w)$ it is not: the target itself depends on $w$, and we deliberately ignore that dependence when taking the gradient.

Dropping that term is what makes it efficient and what makes it dangerous.

The deadly triad

For on-policy linear function approximation, semi-gradient TD converges. But three ingredients, when combined, can make the weights diverge to infinity even on a finite Markov chain.

Each leg alone is safe. On-policy TD with linear approximation converges; tabular off-policy Q-learning converges; MC with any approximator converges (it does not bootstrap). The interaction is the hazard. The simplest divergent example is named after its author.

Geometrically the failure is an expansion. On-policy, the TD update is a contraction in the $d_{\pi }$-weighted norm, so iterates are pulled inward toward a fixed point. Off-policy, the data distribution no longer matches the policy being evaluated; the semi-gradient update can become an expansion, and each step pushes the weights farther out.

The triad is the reason deep RL is hard. Deep Q-networks combine all three legs (a bootstrapped target, off-policy replay, and a neural approximator), and the stabilizing tricks of modern value-based deep RL, target networks and large replay buffers among them, exist precisely to tame this interaction. True-gradient methods that descend the projected Bellman error restore convergence at the cost of a second set of weights.

Putting it together

The whole family is two binary choices: how the target is formed (sample versus bootstrap), and whose policy the target evaluates (behavior versus a different target policy).

The maximization bias

Q-learning's ${\max }_{a^{\prime }}Q(S_{t+1},a^{\prime })$ target has a subtle flaw the full reinforcement-learning subject treats in depth and this lesson glossed: taking a $\max$ over noisy estimates systematically overestimates. Because $\mathbb{E}[{\max }_a{X}_a]\ge {\max }_a\mathbb{E}[X_a]$ whenever the $X_a$ are noisy, the greedy target is biased upward even when every action's true value is identical. If two actions both have true value $0$ but this sample reads $Q(s,a_1)=+0.3$ and $Q(s,a_2)=-0.3$, the correct target is $0$ yet ${\max }_{a}Q(s,a)=+0.3$; averaged over many visits the noise never cancels, because the $\max$ always picks whichever estimate it happened to inflate.

Double Q-learning fixes it by decoupling selection from evaluation. Keep two independent tables $Q_1$ and $Q_2$; use one to select the greedy action and the other to evaluate it, with target $R_{t+1}+\gamma Q_2(S_{t+1},\arg {\max }_{a^{\prime }}{Q}_1(S_{t+1},a^{\prime }))$, alternating which is updated. The noise that inflated the selected action in $Q_1$ is not the noise in $Q_2$'s estimate of it, so the upward bias cancels in expectation.

Double DQN applies exactly this decoupling to the deep-Q-network of the next lesson, using the online network to select and the target network to evaluate, measurably reducing the overestimation that plagues vanilla DQN.

Takeaways

• Model-free methods estimate $v_{\pi }$ or $q_{\pi }$ from sampled transitions, never forming the unknown $P$ and $R$. Both prediction and control reduce to estimating the return ${\mathbb{E}}_{\pi }[G_t]$ from experience.
• Monte Carlo averages complete-episode returns: unbiased, high variance, and blocked in continuing tasks. First-visit and every-visit variants both converge to $v_{\pi }$.
• TD(0) bootstraps, $V(S_t)\leftarrow V(S_t)+\alpha [R_{t+1}+\gamma V(S_{t+1})-V(S_t)]$: online, low variance, biased early, and it exploits the Markov property by fitting the maximum-likelihood model.
• MC control with $\epsilon$-greedy exploration converges to $q_{\star }$ under GLIE (infinite exploration, greedy in the limit).
• SARSA ($R+\gamma Q(S^{\prime },A^{\prime })$) is on-policy and learns a safe path that accounts for its own exploration; Q-learning ($R+\gamma {\max }_{a^{\prime }}Q(S^{\prime },a^{\prime })$) is off-policy and learns the optimal greedy path. Cliff walking separates them.
• n-step returns and TD($\lambda$) interpolate the MC-TD spectrum; the $\lambda$-return averages all $n$-step returns, and eligibility traces give an equivalent online backward-view implementation.
• Semi-gradient TD scales value estimation to parametric $\hat{v}(s;w)$ by SGD on the value error, dropping the target's gradient. Combining bootstrapping, off-policy training, and function approximation, the deadly triad, can diverge, as Baird's counterexample shows. This is the central difficulty of value-based deep RL.
• Maximization bias: the $\max$ target overestimates because $\mathbb{E}[{\max }_a{X}_a]\ge {\max }_a\mathbb{E}[X_a]$ under noise; double Q-learning cancels this by selecting the action with one estimate and evaluating it with an independent one, the idea Double DQN carries into deep RL.