Value-Based Reinforcement Learning

From Tables to Function Approximation

Tabular Q-learning stores one number for every state-action pair:

Q:\mathcal S\times\mathcal A\to\mathbb R.

This works for small finite problems, but not when states are images, state variables are continuous, or most state-action pairs are never observed. A table also treats every pair as unrelated.

We instead learn a parameterized function

Q_\theta(s,a)\approx Q(s,a).

Changing $\theta$ for one example can then change predictions for similar examples. For a discrete action space, a neural network commonly receives a state and emits every action value at once:

f_\theta(s) = \begin{bmatrix} Q_\theta(s,a_1)&\cdots&Q_\theta(s,a_{|\mathcal A|}) \end{bmatrix}.

The greedy action only requires one forward pass:

\pi_\theta(s)=\arg\max_a Q_\theta(s,a).

Value learning as regression

Suppose an oracle supplied the true label $y=Q^\pi(s,a)$ . We could minimize

\ell(\theta) =\frac12\left(y-Q_\theta(s,a)\right)^2.

The resulting gradient update is

\boxed{ \theta \leftarrow \theta+ \alpha\left(y-Q_\theta(s,a)\right) \nabla_\theta Q_\theta(s,a) }.

See derivation

Because the target $y$ is fixed,

\begin{aligned} \nabla_\theta\ell(\theta) &=\frac12\cdot2\left(y-Q_\theta(s,a)\right) \nabla_\theta\left(y-Q_\theta(s,a)\right)\\ &=-\left(y-Q_\theta(s,a)\right) \nabla_\theta Q_\theta(s,a). \end{aligned}

Therefore gradient descent gives

\begin{aligned} \theta &\leftarrow\theta-\alpha\nabla_\theta\ell(\theta)\\ &=\theta+ \alpha\left(y-Q_\theta(s,a)\right) \nabla_\theta Q_\theta(s,a). \end{aligned}

The true value is unavailable, so value-based methods differ mainly in how they construct the target $y$ .

Monte Carlo and temporal-difference targets

After a complete trajectory, Monte Carlo learning uses the sampled return

G_t=\sum_{k=0}^{T-t-1}\gamma^k r_{t+k}.

The update is

\theta\leftarrow\theta+ \alpha\left(G_t-Q_\theta(s_t,a_t)\right) \nabla_\theta Q_\theta(s_t,a_t).

This target is noisy, but it does not depend on another learned value estimate.

For on-policy SARSA,

y_t^{\mathrm{SARSA}} =r_t+\gamma Q_\theta(s_{t+1},a_{t+1}), \qquad a_{t+1}\sim\pi(\cdot\mid s_{t+1}).

For off-policy Q-learning,

\boxed{ y_t^Q =r_t+\gamma\max_{a'}Q_\theta(s_{t+1},a') }.

The Q-learning update is therefore

\boxed{ \theta\leftarrow\theta+ \alpha\delta_t\nabla_\theta Q_\theta(s_t,a_t) },

where

\delta_t =r_t+\gamma\max_{a'}Q_\theta(s_{t+1},a') -Q_\theta(s_t,a_t)

is the temporal-difference error.

For state-value policy evaluation, the same idea gives

w\leftarrow w+ \alpha\left[r_t+\gamma V_w(s_{t+1})-V_w(s_t)\right] \nabla_wV_w(s_t).

If $V_w(s)=w^\top x(s)$ , then $\nabla_wV_w(s)=x(s)$ and

w\leftarrow w+\alpha\delta_t x(s_t).

Why this is a semi-gradient

The Q-learning label contains the network being trained:

y_\theta=r+\gamma\max_{a'}Q_\theta(s',a').

Standard Q-learning deliberately treats $y_\theta$ as fixed during the current update. It differentiates the prediction but not the target. This is a semi-gradient update.

See derivation

Let

a^*=\arg\max_{a'}Q_\theta(s',a')

and define

\delta_\theta =r+\gamma Q_\theta(s',a^*)-Q_\theta(s,a).

Ignoring nondifferentiability at action ties, the full gradient of the squared Bellman error is

\begin{aligned} \nabla_\theta\frac12\delta_\theta^2 &=\delta_\theta\nabla_\theta\delta_\theta\\ &=\delta_\theta \left[ \gamma\nabla_\theta Q_\theta(s',a^*) -\nabla_\theta Q_\theta(s,a) \right]. \end{aligned}

True gradient descent would use

\theta\leftarrow\theta+ \alpha\delta_\theta \left[ \nabla_\theta Q_\theta(s,a) -\gamma\nabla_\theta Q_\theta(s',a^*) \right].

The semi-gradient update omits the second term:

\theta\leftarrow\theta+ \alpha\delta_\theta\nabla_\theta Q_\theta(s,a).

This is not ordinary regression to permanent labels. Updating $\theta$ changes both current predictions and future targets, so learning becomes a moving fixed-point problem.

Fitted Q-Iteration

Exact value iteration repeatedly applies the optimal Bellman operator:

(TQ)(s,a) =r(s,a)+\gamma \mathbb E_{s'\sim P(\cdot\mid s,a)} \left[\max_{a'}Q(s',a')\right].

The optimal action-value function is its fixed point:

Q^*=TQ^*.

With function approximation, the backed-up function may not belong to the representable class. We therefore apply a Bellman backup and regress back into that class:

Q_{k+1}\approx\Pi TQ_k.

Suppose we have a transition dataset

\mathcal D =\{(s_i,a_i,r_i,s_i',d_i)\}_{i=1}^{N},

where $d_i=1$ indicates a true terminal transition. At outer iteration $k$ , freeze the previous Q-function and construct

\boxed{ y_i^{(k)} =r_i+\gamma(1-d_i) \max_{a'}Q_{\theta_k}(s_i',a') }.

We then solve the supervised regression problem

\boxed{ \theta_{k+1} =\arg\min_\theta \frac{1}{2N}\sum_{i=1}^{N} \left[Q_\theta(s_i,a_i)-y_i^{(k)}\right]^2 }.

\textbf{Fitted Q-Iteration}

\begin{aligned} &\text{Collect a transition dataset }\mathcal D.\\[0.25em] &\text{Initialize }Q_{\theta_0}.\\[0.25em] &\text{For }k=0,1,\ldots,K-1:\\[0.25em] &\qquad y_i^{(k)}\leftarrow r_i+\gamma(1-d_i)\max_{a'}Q_{\theta_k}(s_i',a') \quad\forall i,\\[0.25em] &\qquad \theta_{k+1}\leftarrow \arg\min_\theta\frac1{2N}\sum_i \left[Q_\theta(s_i,a_i)-y_i^{(k)}\right]^2.\\[0.25em] &\text{Return }Q_{\theta_K}. \end{aligned}

For fixed $\theta_k$ , the inner loop has stationary labels. This separates target construction from regression and makes the moving-target problem easier to control.

Fitted value iteration would require

\max_a\left[r(s,a)+\gamma \mathbb E_{s'}V(s')\right]

for every candidate action. A sampled transition reveals only the outcome of the action that was taken. Learning $Q(s,a)$ avoids this problem: every transition provides a one-sample target for its observed action, while the next action is evaluated through the learned Q-function.

Let $\mu$ be the behavior policy. Its transition distribution factors as

p_\mu(s,a,r,s') =d_\mu(s)\mu(a\mid s)p(r,s'\mid s,a).

Conditioned on $(s,a)$ , the outcome distribution $p(r,s'\mid s,a)$ does not depend on $\mu$ . The target also uses a greedy next action rather than an action from $\mu$ :

r+\gamma\max_{a'}Q(s',a').

Transitions collected by one policy can therefore train values for a different, greedy policy. However, off-policy learning still requires coverage. No algorithm can infer reliable values for important regions that are absent from the dataset.

Fitted Q-iteration, online Q-learning, and DQN mainly differ in their schedules:

Method	Data	Target refresh	Regression per refresh
Online Q-learning	Latest transition	Every update	One step
DQN	Replay buffer	Slowly through a target network	A few minibatch steps
Fitted Q-iteration	Fixed batch	After an inner fitting phase	Many steps

The Deadly Triad

Approximate value learning becomes especially unstable when it combines:

function approximation, which shares parameters across predictions;
bootstrapping, which uses learned values inside targets;
off-policy learning, which trains under a distribution different from the target policy's distribution.

Each ingredient is valuable. Together, they can produce oscillation or divergence.

The idealized fitted update is

Q_{k+1}=\Pi TQ_k.

The exact Bellman operator is a contraction in the sup norm:

\|TQ-TU\|_\infty \leq\gamma\|Q-U\|_\infty.

But regression usually defines $\Pi$ through a replay-weighted squared loss:

\Pi f =\arg\min_{Q\in\Omega} \mathbb E_{(s,a)\sim d_\mathcal D} \left[(Q(s,a)-f(s,a))^2\right].

This projection is controlled in a distribution-weighted $L_2$ geometry, not necessarily in $L_\infty$ . The regression step can therefore undo the contraction created by the Bellman backup.

Bootstrapping then creates a feedback loop:

\text{value error} \longrightarrow \text{incorrect target} \longrightarrow \text{shared parameter update} \longrightarrow \text{new value errors}.

Off-policy data aggravates the problem. The greedy max may select an action that has weak replay support and a large approximation error:

\text{distribution mismatch} \to \text{poorly constrained value} \to \max\text{ selects the error} \to \text{bootstrapping spreads it}.

Typical symptoms include exploding Q-values, NaNs, oscillating returns, sensitivity to random seeds, and falling Bellman loss without improving policy performance.

Experience Replay

During interaction, we store transitions

(s_t,a_t,r_t,s_{t+1},d_t)

in a finite replay buffer $\mathcal D$ . Training samples random minibatches

\{(s_i,a_i,r_i,s_i',d_i)\}_{i=1}^{B} \sim\mathcal D.

Replay converts an environment stream into an empirical dataset:

\text{interaction} \longrightarrow \text{stored transitions} \longrightarrow \text{random minibatch regression}.

It helps in two ways. First, random batches reduce the short-range temporal correlation in

s_t\to s_{t+1}\to s_{t+2}.

Second, transitions can be reused for many updates. This improves sample efficiency and lets newly learned values propagate backward through older experiences.

Replay does not make data truly independent. It also creates a new training distribution:

\widehat d_\mathcal D(s,a) =\frac1{|\mathcal D|} \sum_{i=1}^{|\mathcal D|} \mathbb 1[(s_i,a_i)=(s,a)].

This is a mixture of many historical behavior policies. Large buffers improve diversity but retain stale experience. Small buffers adapt quickly but forget rare transitions and contain more correlated samples. Uniform sampling can also let common transitions dominate rare failures or rewards.

Most importantly, replay only constrains observed state-action pairs. A greedy policy may exploit high values in unsupported regions, especially in continuous or offline problems.

Target Networks

Naive deep Q-learning uses the same parameters for the prediction and target:

y_\theta=r+\gamma\max_{a'}Q_\theta(s',a').

Every update changes both sides of the regression problem. A target network separates them:

\boxed{ y_i =r_i+\gamma(1-d_i) \max_{a'}Q_{\bar\theta}(s_i',a') },

where $\theta$ is optimized and $\bar\theta$ changes slowly.

For fixed $\bar\theta$ , the loss

L(\theta;\bar\theta) =\frac1{2B}\sum_{i=1}^{B} \left[Q_\theta(s_i,a_i)-y_i\right]^2

is ordinary regression to stationary minibatch labels.

Hard target updates

Every $C$ environment or gradient steps, copy the online parameters:

\boxed{\bar\theta\leftarrow\theta}.

Longer intervals make targets more stable but more stale. Each synchronization also produces an abrupt change in the labels.

Soft target updates

Polyak averaging moves the target gradually:

\boxed{ \bar\theta \leftarrow \rho\bar\theta+(1-\rho)\theta, \qquad \rho\approx1 }.

Some sources instead write

\bar\theta \leftarrow \tau\theta+(1-\tau)\bar\theta, \qquad \tau\ll1.

These are the same update with $\tau=1-\rho$ . Unrolling it shows that the target is an exponentially weighted average of historical online networks:

\bar\theta_t =\rho^t\bar\theta_0 +(1-\rho)\sum_{j=0}^{t-1}\rho^j\theta_{t-j}.

Target networks slow target movement; they do not eliminate it. The Bellman target must also be detached so that gradients do not flow through $Q_{\bar\theta}$ .

Deep Q-Networks

A Deep Q-Network combines:

a neural Q-function $Q_\theta$ ;
an $\epsilon$ -greedy behavior policy;
an experience-replay buffer;
a slowly updated target network $Q_{\bar\theta}$ .

For a sampled transition, the DQN target is

\boxed{ y_i^{\mathrm{DQN}} =r_i+\gamma(1-d_i) \max_{a'}Q_{\bar\theta}(s_i',a') }.

The terminal mask matters. If $d_i=1$ , then $y_i=r_i$ because no future return exists. Time-limit truncations should not automatically be treated as true terminal states when the environment distinguishes them.

The squared Bellman loss is

L_{\mathrm{MSE}}(\theta) =\frac1{2B}\sum_{i=1}^{B} \left[Q_\theta(s_i,a_i)-y_i\right]^2.

Large TD errors produce large gradients. The Huber loss is quadratic near zero and linear for extreme residuals:

\ell_\kappa(\delta) = \begin{cases} \frac12\delta^2,&|\delta|\leq\kappa,\\[4pt] \kappa\left(|\delta|-\frac12\kappa\right),&|\delta|>\kappa. \end{cases}

Its derivative is capped at magnitude $\kappa$ , making individual outliers less destructive.

The behavior policy chooses

a_t= \begin{cases} \text{a uniformly random action},&\text{with probability }\epsilon_t,\\[3pt] \arg\max_aQ_\theta(s_t,a),&\text{with probability }1-\epsilon_t. \end{cases}

We usually start with high exploration and decay $\epsilon_t$ . Decaying too quickly leaves replay concentrated around a poor early policy; decaying too slowly wastes interaction after useful values have emerged.

\textbf{Deep Q-Network}

\begin{aligned} &\text{Initialize replay buffer }\mathcal D\text{ and online parameters }\theta.\\[0.25em] &\bar\theta\leftarrow\theta.\\[0.25em] &\text{For each environment step }t:\\[0.25em] &\qquad a_t\leftarrow\epsilon_t\text{-greedy action from }Q_\theta(s_t,\cdot),\\[0.25em] &\qquad \text{execute }a_t\text{ and observe }(r_t,s_{t+1},d_t),\\[0.25em] &\qquad \mathcal D\leftarrow\mathcal D\cup \{(s_t,a_t,r_t,s_{t+1},d_t)\},\\[0.25em] &\qquad \{(s_i,a_i,r_i,s_i',d_i)\}_{i=1}^{B}\sim\mathcal D,\\[0.25em] &\qquad y_i\leftarrow r_i+\gamma(1-d_i) \max_{a'}Q_{\bar\theta}(s_i',a'),\\[0.25em] &\qquad \theta\leftarrow\arg\min_\theta \frac1B\sum_i\ell\left(y_i-Q_\theta(s_i,a_i)\right),\\[0.25em] &\qquad \text{update }\bar\theta\text{ with a hard copy or Polyak averaging.} \end{aligned}

In practice, we usually delay learning until replay contains enough diverse transitions. We monitor both realized returns and predicted Q-values because training loss alone can be misleading.

Overestimation and Double DQN

Suppose action-value estimates contain zero-mean noise:

\widehat Q(s',a)=Q(s',a)+\varepsilon_a, \qquad \mathbb E[\varepsilon_a]=0.

Even when each action estimate is unbiased,

\boxed{ \mathbb E\left[\max_a\widehat Q(s',a)\right] \geq \max_a\mathbb E\left[\widehat Q(s',a)\right] }.

The maximum preferentially selects positive errors. If two actions both have true value $q$ , then

\max(\widehat Q_1,\widehat Q_2) =q+\max(\varepsilon_1,\varepsilon_2),

whose expectation is larger than $q$ for non-degenerate symmetric noise.

Standard DQN uses the target network both to select and evaluate the action:

\max_{a'}Q_{\bar\theta}(s',a') =Q_{\bar\theta} \left(s',\arg\max_{a'}Q_{\bar\theta}(s',a')\right).

Double DQN decouples these roles. The online network selects the action, while the target network evaluates it:

\boxed{ \begin{aligned} a_i^*&=\arg\max_{a'}Q_\theta(s_i',a'),\\ y_i^{\mathrm{DDQN}} &=r_i+\gamma(1-d_i)Q_{\bar\theta}(s_i',a_i^*). \end{aligned} }

Because the estimators' errors are not identical, positive selection noise is less likely to remain positive during evaluation. This small modification often improves value accuracy.

With two independent critics, clipped double-Q uses

y=r+\gamma(1-d) \min_{j\in\{1,2\}}Q_{\bar\theta_j}(s',a').

The minimum deliberately adds pessimism to counter optimistic feedback. It can also underestimate value, so the goal is stable policy improvement rather than pointwise unbiasedness.

Faster Value Propagation

Deep Q-learning couples three rates:

how quickly transitions enter replay;
how quickly $\theta$ fits the current targets;
how quickly $\bar\theta$ changes those targets.

The update-to-data ratio is

\mathrm{UTD} =\frac{\text{gradient updates}}{\text{new environment transitions}}.

With batch size $B$ , the replay-sample ratio is approximately

B\times\mathrm{UTD}.

A higher UTD extracts more learning from expensive interaction and propagates value faster. But repeatedly fitting a finite buffer can overfit stale data and amplify bootstrapping errors before new experience corrects them.

One-step backups move a delayed reward backward one transition at a time. An $n$ -step target moves it across several transitions:

\boxed{ y_t^{(n)} =\sum_{k=0}^{n-1}\gamma^k r_{t+k} +\gamma^n(1-d_{t:t+n}) \max_aQ_{\bar\theta}(s_{t+n},a) }.

See derivation

Starting from

G_t=r_t+\gamma G_{t+1},

we recursively expand

\begin{aligned} G_t &=r_t+\gamma r_{t+1}+\gamma^2G_{t+2}\\ &=\cdots\\ &=\sum_{k=0}^{n-1}\gamma^k r_{t+k}+\gamma^nG_{t+n}. \end{aligned}

We then bootstrap the remaining return:

G_{t+n}\approx\max_aQ_{\bar\theta}(s_{t+n},a).

Multi-step targets reduce dependence on one-step value estimates and learn faster from delayed reward. They also have higher variance and greater off-policy mismatch because their intermediate rewards were generated by the behavior policy.

Huber loss limits extreme residuals. Gradient clipping separately limits the final parameter gradient:

g\leftarrow \begin{cases} g,&\|g\|_2\leq c,\\[3pt] c\dfrac{g}{\|g\|_2},&\|g\|_2>c. \end{cases}

The first operates on TD errors; the second operates after all chain-rule factors have been combined.

Continuous Actions

DQN can enumerate a finite action set. For $a\in\mathbb R^m$ , both the target

y=r+\gamma\max_{a'}Q(s',a')

and greedy behavior

\pi(s)=\arg\max_aQ(s,a)

require a continuous optimization problem.

One option is iterative gradient ascent in action space:

a^{(j+1)} =\Pi_\mathcal A \left[a^{(j)}+\eta\nabla_aQ_\theta(s,a^{(j)})\right].

This adds an expensive, initialization-sensitive inner loop to every target and action selection.

Sampling actions

Random shooting samples candidates $a_1,\ldots,a_N\sim q(a\mid s)$ and approximates

\max_aQ(s,a) \approx \max_{i=1,\ldots,N}Q(s,a_i).

It is simple and parallelizable, but its sample requirement grows quickly with action dimension.

The cross-entropy method improves the proposal iteratively. Starting with $q_0(a)=\mathcal N(\mu_0,\Sigma_0)$ , it samples actions, keeps an elite set $\mathcal E_j$ , and refits

\mu_{j+1}=\frac1{|\mathcal E_j|} \sum_{i\in\mathcal E_j}a_i,

\Sigma_{j+1} =\frac1{|\mathcal E_j|} \sum_{i\in\mathcal E_j} (a_i-\mu_{j+1})(a_i-\mu_{j+1})^\top.

Each iteration concentrates samples around actions with larger predicted value.

Learning the argmax

Instead of solving a new optimization problem for every state, we can learn an actor

\mu_\psi(s)\approx\arg\max_aQ_\phi(s,a).

The actor maximizes

J(\psi) =\mathbb E_{s\sim\mathcal D} \left[Q_\phi(s,\mu_\psi(s))\right].

By the chain rule,

\boxed{ \nabla_\psi J(\psi) =\mathbb E_{s\sim\mathcal D} \left[ \left.\nabla_aQ_\phi(s,a)\right|_{a=\mu_\psi(s)} \nabla_\psi\mu_\psi(s) \right] }.

The actor amortizes continuous optimization into one forward pass. DDPG uses target actors and critics to construct

\boxed{ y_i =r_i+\gamma(1-d_i) Q_{\bar\phi}(s_i',\mu_{\bar\psi}(s_i')) }.

The critic minimizes

L_Q(\phi) =\frac1{2B}\sum_i \left[Q_\phi(s_i,a_i)-y_i\right]^2,

while the actor ascends $Q_\phi(s,\mu_\psi(s))$ . From this view, deterministic actor-critic is approximate Q-learning in which the actor learns to perform the continuous-action maximization.

Modern methods often use stochastic actors, entropy regularization, and twin critics. These extensions belong to actor-critic methods, but they retain the same value-based core: fit a critic to a slowly moving Bellman target, then improve the policy using that critic.

Why Exact Value Iteration Converges

The optimal Bellman operator is a $\gamma$ -contraction in the sup norm:

\boxed{ \|TQ-TU\|_\infty \leq\gamma\|Q-U\|_\infty }.

See derivation

For state values,

(TV)(s) =\max_a\left[ r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s') \right].

Then

\begin{aligned} |(TV)(s)-(TU)(s)| &\leq\max_a \left| \gamma\sum_{s'}P(s'\mid s,a) [V(s')-U(s')] \right|\\ &\leq\gamma\max_a \sum_{s'}P(s'\mid s,a)|V(s')-U(s')|\\ &\leq\gamma\|V-U\|_\infty \max_a\sum_{s'}P(s'\mid s,a)\\ &=\gamma\|V-U\|_\infty. \end{aligned}

\left|\max_x f(x)-\max_x g(x)\right| \leq\max_x|f(x)-g(x)|.

Taking the maximum over $s$ proves the result. The same argument applies to the Q-Bellman operator.

Because $Q^*=TQ^*$ , exact value iteration satisfies

\begin{aligned} \|Q_{k+1}-Q^*\|_\infty &=\|TQ_k-TQ^*\|_\infty\\ &\leq\gamma\|Q_k-Q^*\|_\infty. \end{aligned}

Therefore,

\boxed{ \|Q_k-Q^*\|_\infty \leq\gamma^k\|Q_0-Q^*\|_\infty }.

This guarantee assumes an exact Bellman backup and a representation that stores every value exactly. Approximate value iteration instead applies $\Pi T$ , and the projection $\Pi$ need not preserve the contraction.

Sampling and Approximation Error

An empirical Bellman operator $\widehat T$ replaces rewards and transitions with finite-sample estimates. A fitted update also incurs regression and optimization error. We can separate the one-step error as

\begin{aligned} \|\widehat Q_{k+1}-T\widehat Q_k\|_\infty &\leq \underbrace{ \|\widehat Q_{k+1}-\widehat T\widehat Q_k\|_\infty }_{\text{approximation and optimization}}\\ &\quad+ \underbrace{ \|\widehat T\widehat Q_k-T\widehat Q_k\|_\infty }_{\text{sampling}}. \end{aligned}

Sampling error decreases at the familiar rate

O\left(\frac1{\sqrt N}\right),

up to reward, horizon, coverage, cardinality, and confidence factors. Approximation error remains when the function class cannot represent the backed-up value or optimization does not find the best fit.

Suppose each approximate backup has bounded error

\|\widehat Q_{k+1}-T\widehat Q_k\|_\infty \leq\varepsilon_k.

Then

\boxed{ \|\widehat Q_k-Q^*\|_\infty \leq \sum_{i=0}^{k-1}\gamma^i\varepsilon_{k-i-1} +\gamma^k\|\widehat Q_0-Q^*\|_\infty }.

See derivation

Since $Q^*=TQ^*$ ,

\begin{aligned} \|\widehat Q_{k+1}-Q^*\|_\infty &=\|\widehat Q_{k+1}-T\widehat Q_k +T\widehat Q_k-TQ^*\|_\infty\\ &\leq\|\widehat Q_{k+1}-T\widehat Q_k\|_\infty +\|T\widehat Q_k-TQ^*\|_\infty\\ &\leq\varepsilon_k +\gamma\|\widehat Q_k-Q^*\|_\infty. \end{aligned}

Applying the recurrence repeatedly gives

\begin{aligned} \|\widehat Q_k-Q^*\|_\infty &\leq\varepsilon_{k-1} +\gamma\varepsilon_{k-2} +\cdots +\gamma^{k-1}\varepsilon_0\\ &\quad+\gamma^k\|\widehat Q_0-Q^*\|_\infty. \end{aligned}

If $\varepsilon_k\leq\varepsilon$ , the limiting error is bounded by

\limsup_{k\to\infty} \|\widehat Q_k-Q^*\|_\infty \leq \boxed{\frac{\varepsilon}{1-\gamma}}.

Thus $1/(1-\gamma)$ acts like an effective horizon that amplifies persistent backup errors. This is one reason value learning becomes harder as $\gamma$ approaches one.

A small empirical Bellman loss only shows that the network fits its current sampled targets on the replay distribution. It does not prove that the targets match the true Bellman operator, unseen actions have accurate values, the projected iteration converges, or the greedy policy achieves high return.

Practical Diagnosis

Symptom	Likely cause	Useful response
Q-values grow while returns stay flat	Overestimation or bootstrapping feedback	Use Double DQN, slower targets, or a lower learning rate
Sudden loss spikes or NaNs	Extreme TD errors or gradients	Check rewards, use Huber loss, and clip gradients
Learning changes sharply at synchronization	Target updates are too abrupt	Increase the hard-update interval carefully or use Polyak updates
Low replay loss but poor behavior	Distribution mismatch or weak coverage	Improve exploration and inspect replay support
Reward propagates too slowly	One-step targets or low UTD	Try n-step returns or modestly increase UTD
Strong seed sensitivity	Unstable approximation and exploration	Simplify, tune conservatively, and evaluate multiple seeds
Continuous-action maximization is slow	Inner optimization is expensive	Learn an actor or use a sampling optimizer

The central value-based recipe is always the same. First construct a bootstrapped target

y=r+\gamma(1-d)\mathcal V(s'),

then fit a critic

L(\theta) =\mathbb E_\mathcal D \left[\ell\left(y-Q_\theta(s,a)\right)\right]

without differentiating through the target. Finally, update the target estimator slowly.

The hard part is not writing this loss. It is keeping sampling error, approximation error, distribution shift, maximization bias, and target movement from reinforcing one another.