From tables to networks: why better regression can mean worse values

The Bellman chapter established convergence for exact tabular iteration under discounting and bounded rewards. Why does replacing the table with a neural network change the conclusion? Every update must now fit back into a restricted function class.

Fitted Q-iteration makes labels, then fits them

Fix transitions $\mathcal D=\{(s_i,a_i,r_i,s'_i,d_i)\}$, where $d_i$ means true termination. At each iteration, construct labels with the previous function:

$$ y_i^{(k)}=r_i+\gamma(1-d_i)\max_{a'}Q_k(s'_i,a'), \qquad Q_{k+1}\in\arg\min_{Q\in\mathcal F}\sum_i\left(Q(s_i,a_i)-y_i^{(k)}\right)^2. $$

This is fitted Q-iteration (FQI). Labels remain fixed within a regression round and change at the next round. DQN performs related approximate iterations using replay, gradient steps, and periodic target updates, rather than solving each regression exactly.

The extra operation is a projection

Temporarily ignore finite-sample and optimization errors. Write regression as a projection $\Pi_\mu$, where $\mu$ is the fitting distribution:

$$ Q_{k+1}=\Pi_\mu\mathcal TQ_k. $$

The Bellman operator $\mathcal T$ is a $\gamma$-contraction in the maximum norm $\|\cdot\|_\infty$. Least-squares orthogonal projection onto a linear function space is nonexpansive in the corresponding weighted $L_2(\mu)$ norm. Those guarantees use different norms and cannot simply be multiplied.

With a nonconvex neural function class, projection may also be nonunique and optimization may miss its optimum. Even the ideal linear-projection properties no longer apply automatically. This does not mean all function approximation diverges: specific function classes, distributions, and algorithms can still admit convergence guarantees, such as LSTD with linear features.

A two-state counterexample

Consider a value-iteration counterexample that follows Tsitsiklis and Van Roy's classic construction (with $\varepsilon=0$; Sutton & Barto §11.2 also covers it): both states transition deterministically to state 2, all rewards are zero, and $\gamma=0.9$. There is one action per state, so Q and V are equivalent and the true values are both zero.

Restrict the representation to $V_\theta=[\theta,2\theta]$ and give the states equal fixed regression weight. Bellman labels are $[1.8\theta_k,1.8\theta_k]$. Exact least squares gives:

$$ \theta_{k+1} =\arg\min_u\left[(u-1.8\theta_k)^2+(2u-1.8\theta_k)^2\right] =1.08\theta_k. $$

Starting at $\theta_0=1$, multiplying by 1.08 each round moves away from zero. The true answer is in the function class, yet the iteration still fails.

In the first regression, mean squared error against the same old labels falls from 0.34 to 0.324. The inner fit really improves. But labels change next round, so this is not progress toward the true value function.

The fixed uniform fitting distribution is not this Markov process's stationary distribution, which concentrates on state 2. This example does not show that all on-policy TD diverges. It refutes unconditional inheritance of tabular convergence for arbitrary sampling distributions and projections.

What changes if we only change the discount?

The general recurrence is $\theta_{k+1}=1.2\gamma\theta_k$. At $\gamma=0.5$, the multiplier is 0.6 and this example converges. Lowering the discount also changes how much the task values the future, so it is not a free fix. The accompanying Python checks verify both cases.

Gradient descent on which objective?

FQI may use gradient descent to fit each fixed set of labels. Q-learning's semi-gradient is also the gradient against its current fixed target. The outer targets change with Q, however: neither is full gradient descent on one permanently fixed overall Bellman residual.

Differentiating $\mathbb E[(Q-\mathcal TQ)^2]$ fully introduces estimation of products of conditional expectations under stochastic transitions. Reusing one next-state sample for both terms is generally insufficient. This double-sampling issue is different from Double DQN's separation of action selection and evaluation.

Why can one next-state sample miss the full gradient?

Set aside the RL notation. Let $Y_\theta$ be a random target and $c_\theta$ the current prediction. The intended squared residual against the expected target is:

$$ L(\theta)=(c_\theta-\mathbb E[Y_\theta])^2. $$

Squaring a single sampled residual instead gives:

$$ \mathbb E[(c_\theta-Y_\theta)^2] =(c_\theta-\mathbb E[Y_\theta])^2+\operatorname{Var}(Y_\theta). $$

If target variance depends on parameters, that extra term has a gradient. For $c_\theta=0$ and a target equally likely to be $+\theta$ or $-\theta$, the intended residual is always zero, while expected sample-squared error is $\theta^2$. The update also optimizes variance.

A full Bellman-residual gradient contains a product involving conditional expectations of the residual and target derivative. Reusing one transition for both generally introduces dependence. Independent next-state samples can address the product, but a real environment may not let you resample exactly the same state–action pair. Semi-gradients avoid part of this computation by changing the update, not by becoming unbiased full gradients.

Which error decreased when the loss fell?

A larger model mainly changes representation capacity, not missing data. More gradient steps mainly improve the current regression, not necessarily the outer iteration. The two-state example diverges even with exact inner fitting, separating these concerns.

Each stabilization component addresses one problem

Reference: A classic batch fitted Q-iteration method. The two-state calculation above follows Tsitsiklis and Van Roy's classic counterexample; it is not an experimental result from that paper. Continue with DQN implementation and checks.