Why Tabular TD(0) Converges
Supplement to Lecture 32: Value-Based Model-Free RL
Temporal-difference (TD) learning updates an estimate using another estimate. Why does that lead to the true value rather than preserving the initial errors?
We prove convergence of tabular TD(0) for a fixed policy. The proof uses sampled transitions along Markov trajectories, including repeated episodes. It separates a TD update into a Bellman correction and sampling noise, shows that the accumulated effect of the noise vanishes, and then uses discounting to eliminate the remaining error.
The TD(0) update
Fix a policy \pi. Its true value v_\pi(s) is the expected discounted return when starting from s and following \pi:
v_\pi(s)=\mathbb E_\pi\!\left[ \sum_{k=0}^{\infty}\gamma^k R_{k+1} \;\middle|\; S_0=s\right].
Here k counts steps along the trajectory, R_{k+1} is the reward on its next transition, and \gamma is the discount factor. For an episodic task, rewards after termination are zero in this definition. We are evaluating a policy, not searching for the optimal one.
TD(0) keeps one estimate per state in a table V_t. The index t counts training updates across all episodes. In sample t, the current state is S_t, the reward is R_{t+1}, and the observed successor is S'_t. The successor need not be the next update’s current state S_{t+1}: if the episode ends, the next update starts a new episode.
From a finite, deterministic initial table V_0, update only the entry for S_t:
\begin{aligned} \delta_t &= R_{t+1}+\gamma V_t(S'_t)-V_t(S_t),\\ V_{t+1}(S_t)&=V_t(S_t)+\alpha_t\delta_t . \end{aligned}
\delta_t is the TD error: the sampled target minus the current estimate. \alpha_t is the learning rate. A terminal state’s value is fixed at zero, so an update that enters a terminal state uses just the observed reward as its target.
Assumptions and result
| Assumption | Why it matters |
|---|---|
| The state space is finite and the values are tabular. | We can represent the exact values and bound the largest error over the whole table. |
| Actions are sampled from a fixed policy in a time-homogeneous Markov environment. | Given the current state, the policy and environment give the same conditional law for the next transition throughout training. |
| 0\le\gamma<1. | Discounting makes the Bellman operator contract errors. |
| Rewards are bounded: \lvert R_{t+1}\rvert\le R_{\max}. | Values and sampling noise stay bounded. |
| Every learned state is updated infinitely often, with suitable learning rates. | Each entry receives enough updates to forget its initial error without letting noise accumulate indefinitely. |
Let a_t(s)=\alpha_t\mathbf 1\{S_t=s\} be the learning rate actually applied to entry s at time t. The indicator is 1 when that entry is updated and 0 otherwise. For each learned state, require, with probability one,
\begin{gathered} 0\le a_t(s)\le 1,\\ \sum_{t=0}^{\infty}a_t(s)=\infty,\qquad \sum_{t=0}^{\infty}a_t(s)^2<\infty. \end{gathered}
These Robbins–Monro conditions give an infinite total learning rate, but a finite total squared learning rate. A simple choice is \alpha_t=1/k on the k-th visit to the current state. Count visits to that state, not the total number of updates. Choose the rate before sampling the current transition. In episodic tasks these conditions apply only to learned (nonterminal) states.
Under these assumptions, V_t(s)\to v_\pi(s) for every state s, almost surely (with probability one). This is a statement about the limit, not a claim that every update improves the estimate.
A one-state example
Suppose every step gives reward 1 and returns to the same state. With \gamma=0.9, the true value satisfies v=1+0.9v, so v=10. Starting at V=0, full bootstrap updates V\leftarrow 1+0.9V give:
0\to 1\to 1.9\to 2.71\to\cdots\to10 .
The target uses an imperfect estimate, yet the sequence converges. This deterministic example illustrates bootstrapping; the proof also handles random rewards, random next states, and one-entry-at-a-time updates.
Bellman notation
Let P=P_\pi be the transition matrix under policy \pi, so P(s,s') is the probability of going from s to s'. A terminal state is treated as absorbing with zero further reward. Resets are not transitions in P; they provide starting states for new samples. Let r(s) be the expected immediate reward at s.
For any vector x, define its sup norm as \lVert x\rVert_\infty=\max_s\lvert x(s)\rvert. Since (Px)(s) is a weighted average,
\begin{gathered} (Px)(s)=\sum_{s'}P(s,s')x(s'),\\ \lvert (Px)(s)\rvert\le\lVert x\rVert_\infty . \end{gathered}
The Bellman operator gives the expected one-step target for a table V. The true value is its fixed point:
T^\pi V=r+\gamma PV,\qquad v_\pi=T^\pi v_\pi .
The proof tracks four quantities that the algorithm itself does not compute:
| Symbol | Meaning |
|---|---|
| e_t=V_t-v_\pi | The true value-estimation error. |
| \eta_{t+1} | The sampled target minus its conditional expectation. |
| z_t | The accumulated effect of the noise after averaging. |
| y_t=e_t-z_t | The error remaining after removing z_t. Here y_t is an error vector, not the TD target. |
Step 1: Bound the estimates
Set
B=\max\!\left\{\lVert V_0\rVert_\infty,\frac{R_{\max}}{1-\gamma}\right\}.
R_{\max} bounds the magnitude of a reward. For example, we can take R_{\max}=5 if all rewards lie in [-5,-1]. The argument also covers R_{\max}=0.
If \lVert V_t\rVert_\infty\le B, every sampled target has magnitude at most R_{\max}+\gamma B\le B. The updated entry is a convex combination, an average with nonnegative weights that sum to one:
\begin{aligned} V_{t+1}(S_t)={}&(1-\alpha_t)V_t(S_t)\\ &+\alpha_t\big[R_{t+1}+\gamma V_t(S'_t)\big]. \end{aligned}
Both quantities being averaged lie in [-B,B]. The other entries do not change, so \lVert V_t\rVert_\infty\le B for every t by induction. Also \lVert v_\pi\rVert_\infty\le R_{\max}/(1-\gamma)\le B, so e_t is bounded.
Step 2: Separate the correction from the noise
Let \mathcal F_t be the information available at the current state: the past, S_t, V_t, and the chosen learning rate. It excludes the current action, reward, and successor state, which have not yet been sampled.
The conditional mean of the sampled target is (T^\pi V_t)(S_t). Define the difference:
\begin{aligned} \eta_{t+1}={}&R_{t+1}+\gamma V_t(S'_t)\\ &-(T^\pi V_t)(S_t),\\ \mathbb E[\eta_{t+1}\mid\mathcal F_t]={}&0. \end{aligned}
The target and its conditional mean both lie in [-B,B], so \lvert\eta_{t+1}\rvert\le 2B. Conditional mean zero does not require independent transitions. Consecutive samples can be correlated.
The TD error is therefore
\delta_t=(T^\pi V_t)(S_t)-V_t(S_t)+\eta_{t+1}.
To get the error update, first write the estimated-value update for any state:
\begin{aligned} V_{t+1}(s)={}&(1-a_t(s))V_t(s)\\ &+a_t(s)\big[(T^\pi V_t)(s)+\eta_{t+1}\big]. \end{aligned}
The scalar noise comes from the transition at S_t. For every other state, a_t(s)=0, so it has no effect there.
The Bellman equation gives the matching identity for the true value:
\begin{aligned} v_\pi(s)={}&(1-a_t(s))v_\pi(s)\\ &+a_t(s)(T^\pi v_\pi)(s). \end{aligned}
Subtract the identities. The r(s) terms cancel, and linearity gives PV_t-Pv_\pi=P(V_t-v_\pi)=Pe_t. Thus
\begin{aligned} e_{t+1}(s)={}&(1-a_t(s))e_t(s)\\ &+a_t(s)\gamma(Pe_t)(s)\\ &+a_t(s)\eta_{t+1}. \end{aligned} \tag{1}
The new error combines the old entry, a discounted average of other entries’ errors, and sampling noise. We need to control both the averaging and the noise.
Step 3: Show that accumulated noise vanishes
Define an auxiliary process starting at z_0(s)=0:
\begin{aligned} z_{t+1}(s)={}&(1-a_t(s))z_t(s)\\ &+a_t(s)\eta_{t+1}. \end{aligned} \tag{2}
Equation (2) uses the same old-value weight and noise term as (1). Later we subtract it to cancel the raw noise. Since the updates are convex combinations of bounded quantities, \lvert z_t(s)\rvert\le 2B.
The Robbins–Siegmund lemma
We use the following form of the Robbins–Siegmund lemma. Suppose X_t\ge 0 has finite expectation and is adapted to \mathcal F_t, meaning its value is known at time t. Suppose
\mathbb E[X_{t+1}\mid\mathcal F_t]\le X_t-b_t+c_t,
where b_t,c_t are nonnegative and known at time t. If \sum_t c_t<\infty almost surely, then X_t converges to a finite limit and \sum_t b_t<\infty almost surely. In our application, the deterministic bounds ensure the expectations exist.
Apply the lemma
Fix a state s and write a=a_t(s) and z=z_t(s). Square (2) and take the conditional expectation. The cross term 2a(1-a)z\,\mathbb E[\eta_{t+1}\mid\mathcal F_t] is zero. With C=4B^2, the remaining terms satisfy
\begin{aligned} &\mathbb E[z_{t+1}(s)^2\mid\mathcal F_t]\\ &\quad=(1-a)^2 z^2 +a^2\mathbb E[\eta_{t+1}^2\mid\mathcal F_t]\\ &\quad\le (1-a)z^2+C a^2\\ &\quad= z^2-a z^2+C a^2. \end{aligned}
Here we used (1-a)^2\le 1-a and \lvert\eta_{t+1}\rvert\le 2B. Apply the lemma with X_t=z_t(s)^2, b_t=a_t(s)z_t(s)^2, and c_t=C a_t(s)^2. The squared learning rates are summable, so z_t(s)^2 converges and \sum_t a_t(s)z_t(s)^2<\infty almost surely.
The limit cannot be positive. If it were \ell>0, then eventually z_t(s)^2\ge\ell/2. Since the tail sum of a_t(s) is infinite, the sum of a_t(s)z_t(s)^2 would be infinite too, a contradiction. Thus z_t(s)\to 0 almost surely. There are finitely many states, so \lVert z_t\rVert_\infty\to0 almost surely.
What vanishes is the accumulated effect of the averaged noise. Individual noise samples \eta_{t+1} can stay large.
Step 4: Show that the remaining error vanishes
Set y_t=e_t-z_t. Subtract (2) from (1) and substitute e_t=y_t+z_t:
\begin{aligned} &y_{t+1}(s)=(1-a_t(s))y_t(s)\\ &\quad+a_t(s)\gamma[P(y_t+z_t)](s). \end{aligned} \tag{3}
Both e_t and z_t are bounded, so y_t is bounded. Let L=\limsup_{t\to\infty}\lVert y_t\rVert_\infty, the largest error level that recurs arbitrarily late. Work on a sample path where \lVert z_t\rVert_\infty\to0 and the learning-rate conditions hold. For any \varepsilon>0, choose T large enough that for all t\ge T,
\lVert y_t\rVert_\infty\le L+\varepsilon,\qquad \lVert z_t\rVert_\infty\le\varepsilon .
Because P takes weighted averages, the target in (3) has magnitude at most C_\varepsilon=\gamma(L+2\varepsilon). Each entry averages its old value with these bounded targets. Iterating (3) in absolute value gives
\lvert y_t(s)\rvert \le C_\varepsilon+\lvert y_T(s)\rvert \prod_{u=T}^{t-1}(1-a_u(s)).
The product is the surviving weight of the old entry. By 1-x\le e^{-x},
\begin{gathered} \prod_{u=T}^{t-1}(1-a_u(s))\\ \le \exp\!\left(-\sum_{u=T}^{t-1}a_u(s)\right) \longrightarrow 0 . \end{gathered}
The upper bound goes to zero because \sum_u a_u(s)=\infty for each learned state. Therefore \limsup_t\lvert y_t(s)\rvert\le C_\varepsilon. Terminal entries are already zero. Since there are finitely many states, we can take the maximum:
L=\max_s\limsup_{t\to\infty}\lvert y_t(s)\rvert \le \gamma(L+2\varepsilon).
Letting \varepsilon go to zero gives L\le\gamma L. Since L\ge0 and \gamma<1, this forces L=0. Hence y_t\to0 on every such sample path.
Conclusion
We proved that both z_t and y_t converge to zero almost surely. Since V_t-v_\pi=e_t=y_t+z_t, we have V_t(s)\to v_\pi(s) for every state, almost surely.
The noise-filtering argument is a bounded-reward, no-delay version of the asynchronous stochastic-approximation approach in Tsitsiklis (1994), Asynchronous Stochastic Approximation and Q-Learning (Lemma 1 and Theorem 3).
What TD error tells us
Holding the current table fixed, the conditional mean of the TD error is
\mathbb E[\delta_t\mid\mathcal F_t] =(T^\pi V_t)(S_t)-V_t(S_t).
TD error is a noisy observation of Bellman inconsistency: the gap between the expected one-step target and the current estimate. Its conditional mean is generally not the true estimation error v_\pi(S_t)-V_t(S_t).
At the correct value, the conditional mean TD error is zero at each state, but individual sampled errors can still be nonzero. Neither a single sampled error nor a small signed average across different states certifies that the table is correct: positive and negative errors can cancel.