A Bellman backup computes the expected one step lookahead value of a state: reward now, plus discounted value of wherever you land, averaged over where you might land. If you cannot compute that average because you do not know the landing distribution, the obvious substitute is to take the step once and use where you actually landed. That single sample is an unbiased estimate of the expectation. Temporal difference learning is dynamic programming with each expectation replaced by one sample, and a step size to average the samples over time.

The other idea in play is bootstrapping: the target for updating $V(s_t)$ uses the current estimate $V(s_{t+1})$ rather than waiting for the true return. Monte Carlo methods wait for the episode to end and use the actual return $G_t$, which is unbiased but has variance from every future step. TD uses a target with one step of sampled randomness and then trusts its own estimate for the rest. That trades a little bias, since $V(s_{t+1})$ is not yet correct, for a large reduction in variance, and it works for continuing tasks where there is no episode end to wait for.

TD(0) for policy evaluation

Fix a policy $\pi$ and let the agent follow it. On observing the transition $(s_t, a_t, r_{t+1}, s_{t+1})$, update

The bracketed quantity is the TD error,

the gap between the current estimate and the one step bootstrapped target. The update moves the estimate a fraction $\alpha_t$ of the way toward the target.

What the update is estimating. Take the expectation of the target over the transition, holding $V$ fixed:

So the sampled target is an unbiased estimate of the Bellman expectation backup, and the TD(0) update is a stochastic approximation of the fixed point iteration $V \leftarrow \mathcal{T}^\pi V$. That reframing is the entire content of the convergence proof below.

SARSA: on policy control

To improve the policy rather than just evaluate it, learn action values. SARSA updates $Q$ toward the one step target using the action actually taken next:

The name is the tuple it consumes: state, action, reward, state, action. The behavior policy is typically $\epsilon$ greedy with respect to the current $Q$: take the greedy action with probability $1 - \epsilon$ and a uniformly random one otherwise. Because $a_{t+1}$ is drawn from that same policy, the target estimates $Q^{\pi}$ for the policy being followed, exploration included. SARSA is on policy: it evaluates and improves the policy that is generating the data.

For SARSA to converge to $Q^*$ rather than to the value of some exploratory policy, the behavior policy has to become greedy over time while still exploring enough. The standard condition is GLIE, greedy in the limit with infinite exploration: every state action pair is visited infinitely often, and the policy converges to the greedy policy. Decaying $\epsilon_t = 1 / t$ satisfies it. Under GLIE and the step size conditions below, SARSA converges to $Q^*$ (Singh, Jaakkola, Littman, Szepesvári 2000).

Q learning: off policy control

Q learning (Watkins 1989) targets the optimality operator directly:

The target uses the best action at the next state according to the current $Q$, regardless of which action the behavior policy actually takes next. Holding $Q$ fixed and averaging over the transition,

so Q learning is a stochastic approximation of $Q \leftarrow \mathcal{T}^* Q$, whose fixed point is $Q^*$. It is off policy: the data can come from any behavior policy that keeps visiting every state action pair, and $Q$ still converges to the optimal action values. The behavior policy only affects which pairs get updated and how often, not what they converge to.

Why the distinction matters

The two algorithms differ by one symbol, $Q(s_{t+1}, a_{t+1})$ against $\max_{a'} Q(s_{t+1}, a')$, and they learn different things. The cliff walking example from Sutton and Barto makes it concrete. The shortest path to the goal runs along the edge of a cliff; stepping off costs a large penalty. Q learning learns the value of the cliff edge path assuming optimal future behavior, so it rates that path highly and follows it, and during training an $\epsilon$ greedy agent following it regularly falls off. SARSA's target includes the exploratory action, so it learns that the cliff edge is dangerous for the policy actually being run and prefers a longer, safer route. Q learning finds the optimal policy for the deterministic greedy agent. SARSA finds the optimal policy for the agent that is actually exploring.

Convergence of Q learning

Theorem (Watkins and Dayan 1992; Tsitsiklis 1994; Jaakkola, Jordan, Singh 1994). Consider a finite MDP with bounded rewards and $\gamma < 1$. Suppose

1. every state action pair is updated infinitely often, and
2. the step sizes satisfy the Robbins Monro conditions for each pair, $\sum_t \alpha_t(s, a) = \infty$ and $\sum_t \alpha_t(s, a)^2 < \infty$.

Then the Q learning iterates converge to $Q^*$ with probability one.

The two step size conditions say that the steps are large enough in total to get anywhere, but shrink fast enough that the noise averages out. A step size $\alpha_t = 1 / n_t(s, a)$, the reciprocal of the visit count, satisfies both. A constant step size satisfies neither and gives convergence to a neighborhood rather than to the point.

The stochastic approximation lemma

The proof reduces to a general result about noisy contraction iterations.

Lemma. Let $\Delta_t$ be a random process on $\mathbb{R}^n$ updated componentwise by

where $x$ ranges over the components, $\mathcal{F}_t$ is the history up to time $t$, and

• the step sizes satisfy $0 \le \alpha_t(x) \le 1$, $\sum_t \alpha_t(x) = \infty$, $\sum_t \alpha_t(x)^2 < \infty$;
• the update is a contraction in expectation, $\|\mathbb{E}[F_t(x) \mid \mathcal{F}_t]\|_\infty \le \gamma \|\Delta_t\|_\infty$ for some $\gamma < 1$;
• the noise has bounded variance, $\mathrm{Var}[F_t(x) \mid \mathcal{F}_t] \le C(1 + \|\Delta_t\|_\infty)^2$.

Then $\Delta_t \to 0$ with probability one.

The lemma is proved in Jaakkola, Jordan and Singh (1994). The idea of the proof is that the iteration can be sandwiched: the conditional mean pulls $\|\Delta_t\|_\infty$ down by a factor $\gamma$ per effective step, while the zero mean noise, under the square summable step sizes, contributes a martingale whose total effect is finite. The sup norm therefore decreases to zero through a sequence of shrinking levels. It is the Banach fixed point argument with the deterministic contraction replaced by a contraction in conditional expectation.

Applying the lemma to Q learning

Set $\Delta_t(s, a) = Q_t(s, a) - Q^*(s, a)$. Subtract $Q^*(s, a)$ from both sides of the Q learning update:

where

Contraction in expectation. Taking the conditional expectation over the transition and using $Q^* = \mathcal{T}^* Q^*$,

and since $\mathcal{T}^*$ is a $\gamma$ contraction in the sup norm, $\|\mathbb{E}[F_t \mid \mathcal{F}_t]\|_\infty \le \gamma \|Q_t - Q^*\|_\infty = \gamma \|\Delta_t\|_\infty$.

Bounded variance. $F_t(s, a)$ is a bounded reward plus $\gamma$ times a max over entries of $Q_t$, minus a constant. Its conditional variance is bounded by a constant times $(1 + \|\Delta_t\|_\infty)^2$, because $Q_t = Q^* + \Delta_t$ and $Q^*$ is bounded.

The step size conditions are assumed. The lemma applies, $\Delta_t \to 0$, and $Q_t \to Q^*$ with probability one. $\square$

The structure of the argument is the thing to remember. Q learning converges because $\mathcal{T}^*$ is a contraction, the sampled target is unbiased for $\mathcal{T}^* Q_t$, and the step sizes are chosen so that the noise averages out. All three are needed, and the contraction is doing the same job it did in the deterministic case.

The same reduction proves TD(0) converges to $V^\pi$, with $\mathcal{T}^\pi$ in place of $\mathcal{T}^*$, and SARSA under GLIE, with an additional argument that the target operator converges to $\mathcal{T}^*$ as the policy becomes greedy.

Function approximation

Everything above is tabular: one number per state or state action pair. For large or continuous spaces, $Q$ is replaced by a parametric function $Q_\phi(s, a)$ and the TD update becomes a gradient step on the squared TD error with the target held fixed:

This is a semi gradient: the target depends on $\phi$ too, but its dependence is ignored. Two things are lost. The projection onto the function class is not in general a sup norm contraction, and the sampled states follow the behavior distribution rather than being swept uniformly. The combination of bootstrapping, off policy data and function approximation, which Sutton and Barto call the deadly triad, can diverge even for linear function approximation, and there are classic counterexamples (Baird 1995) that do.

Deep Q networks (Mnih et al. 2015) do not resolve this in theory but manage it in practice with two devices. A target network, a lagged copy of the parameters used only in the target, breaks the feedback between the estimate and its own target. Experience replay stores transitions and trains on random minibatches, decorrelating consecutive updates and reusing data. Double DQN, dueling architectures and prioritized replay refine the same recipe.

Where this breaks

• Convergence is asymptotic and the proof says nothing about rate. Q learning can be extremely slow when $\gamma$ is close to one, and its finite sample behavior is a separate, harder literature.
• The max in the Q learning target introduces an overestimation bias: the max of noisy estimates is biased upward. Double Q learning (van Hasselt 2010) decouples selection from evaluation to remove it.
• The guarantees are tabular. With function approximation, convergence holds for on policy linear TD (Tsitsiklis and Van Roy 1997) and is not guaranteed for the off policy nonlinear case that is actually used.

Where value methods struggle, in continuous action spaces where the max over actions is itself an optimization problem, or where a stochastic policy is needed, the alternative is to parameterize the policy and differentiate the objective directly. That is the Policy gradient theorem.

References

• Sutton. Learning to Predict by the Methods of Temporal Differences. Machine Learning, 1988.
• Watkins. Learning from Delayed Rewards. PhD thesis, Cambridge, 1989.
• Watkins, Dayan. Q-Learning. Machine Learning, 1992.
• Jaakkola, Jordan, Singh. On the Convergence of Stochastic Iterative Dynamic Programming Algorithms. Neural Computation, 1994.
• Tsitsiklis. Asynchronous Stochastic Approximation and Q-Learning. Machine Learning, 1994.
• Singh, Jaakkola, Littman, Szepesvári. Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms. Machine Learning, 2000.
• Mnih et al. Human-Level Control through Deep Reinforcement Learning. Nature, 2015.
• Sutton, Barto. Reinforcement Learning: An Introduction, 2nd ed. MIT Press, 2018, chapters 6 and 11.