Appearance
Value-Based Learning: From Dynamic Programming to DQN
In one sentence: this page covers the complete story of value-based RL — learn a value function (V or Q) first, then derive a policy from it. The journey runs from dynamic programming with a known model, through model-free Monte Carlo and temporal-difference learning, to the DQN family of the deep era. By the end, you'll be able to hand-write a tabular Q-learning algorithm, explain the TD error, and articulate why every engineering trick in DQN is there.
1. The Big Picture: Learn Q, Then Derive the Policy
1. The Core Logic
The idea behind value-based learning is almost embarrassingly simple — just three steps:
text
Value-Based Learning in Three Steps
─────────────────────────────────────────────
Step 1: learn a value function Q(s,a) ("what each action is worth")
Step 2: policy = argmax_a Q(s,a) ("pick the most valuable action")
Step 3: keep improving Q from (s, r, s') experience
─────────────────────────────────────────────In other words, the value function is the star of the show; the policy is a sidekick, derived automatically from Q. This is the exact opposite of policy gradient methods, where the policy is learned directly and the value function — if it exists at all — plays a supporting role.
2. Learning Q Means Solving the Bellman Equation
Recall the Bellman optimality equation from the Markov decision process (MDP) page:
$$ Q^(s,a) = \sum_{s'} P(s' \mid s,a) \left[ R(s,a,s') + \gamma \max_{a'} Q^(s', a') \right] $$
The entire history of value-based learning is one long answer to the question "how do we solve this equation?" Ordered by how much information each method uses while solving it:
| Era | What information is used | Representative methods |
|---|---|---|
| Dynamic programming | The full model P, R | Policy iteration, value iteration |
| Sampling era | Samples from interacting with the environment | MC, TD(0), SARSA, Q-learning |
| Deep era | Samples + neural networks | DQN and its family |
2. When the Model Is Known: Dynamic Programming (DP)
1. Policy Iteration: Evaluate → Improve → Evaluate → Improve
Policy iteration alternates between two steps:
text
┌───────────────┐ ┌───────────────┐
│ Policy │ │ Policy │
│ Evaluation │ ──────▶ │ Improvement │
│ solve V^π via │ │ π' = greedy │
│ Bellman │ ◀────── │ (argmax on │
│ iteration │ │ V^π) │
└───────────────┘ └───────────────┘
▲ │
└────until the policy stops changing────┘- Policy evaluation: given a policy π, iterate the Bellman equation to compute $V^\pi$:
$$ V_{k+1}(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a)\left[ R + \gamma V_k(s') \right] $$
- Policy improvement: once you have $V^\pi$, turn the policy "greedy with respect to the value":
$$ \pi'(s) = \arg\max_a \sum_{s'} P(s'|s,a) [R + \gamma V^\pi(s')] $$
The policy improvement theorem guarantees that the new policy π' is never worse than π. Keep repeating until you hit a fixed point → the optimal policy.
2. Value Iteration: Evaluation and Improvement Merged into One Step
Value iteration cuts out the "evaluate until convergence" phase and performs a single Bellman optimality update per round:
$$ V_{k+1}(s) = \max_a \sum_{s'} P(s'|s,a)\left[ R(s,a,s') + \gamma V_k(s') \right] $$
The intuition: value iteration "evaluates and improves at the same time" — every value update implicitly swaps in a new policy.
3. Policy Iteration vs. Value Iteration
| Dimension | Policy iteration | Value iteration |
|---|---|---|
| What each round does | Full evaluation + one improvement | One Bellman update (improvement implicit) |
| Number of rounds | Few (but each round is expensive) | Many (but each round is cheap) |
| Convergence speed | Usually faster | Slower; needs many rounds |
| When to use | Small state spaces, accurate models | Same as above |
Why DP still matters in practice
Real problems rarely come with a perfect model, so DP is seldom used as-is in practice. But it is the theoretical baseline for all value-based learning: Q-learning replaces the summations in DP with sampling, and the target computation in DDPG/SAC is at heart a single Bellman backup. Only by understanding DP can you see what every later "approximation" adds — and what it gives up.
3. When the Model Is Unknown: Monte Carlo (MC) and Temporal-Difference (TD)
In reality we don't have access to $P$ and $R$, but the agent can interact with the environment to collect samples. MC and TD do exactly that — they replace the model with samples.
1. Monte Carlo: Finish the Whole Episode, Then Look Back
The Monte Carlo intuition: "How much is this state worth? Play a few more episodes and see how much you win on average from this state onward."
For every complete trajectory ${s_0,a_0,r_1,s_1,\dots,r_T}$, compute the return $G_t = r_{t+1}+\gamma r_{t+2}+\cdots$ for each visited state, then average it into $V(s_t)$:
$$ V(s_t) \leftarrow V(s_t) + \alpha \left( G_t - V(s_t) \right) $$
Properties: unbiased ($G_t$ is a sample mean of the true return), high variance (a single trajectory carries a lot of luck), and updates must wait until the episode ends (episodic tasks only).
2. TD: Update After a Single Step (Bootstrapping)
The temporal-difference (TD) intuition: "I don't have to wait for the ending. Take one step, see what actually happened, and correct my current estimate with this step's experience plus my estimate of what comes next."
$$ V(s_t) \leftarrow V(s_t) + \alpha \left[ r_{t+1} + \gamma V(s_{t+1}) - V(s_t) \right] $$
The expression in brackets is the TD error:
$$ \delta_t = r_{t+1} + \gamma V(s_{t+1}) - V(s_t) $$
Intuitively, $\delta_t$ measures the gap between "I thought state s_t was worth $V(s_t)$" and "after taking one step, it looks like it should be worth $r_{t+1} + \gamma V(s_{t+1})$" — that gap is the direction of the correction. A positive TD error means "better than expected"; a negative one means "worse than expected."
3. MC vs. TD at a Glance
| Dimension | MC | TD(0) |
|---|---|---|
| When updates happen | End of episode | Every step |
| Bias | Unbiased | Biased (relies on the current estimate of $V(s_{t+1})$) |
| Variance | High (the luck of the whole trajectory is baked in) | Low (only one step of randomness) |
| Requires episode end | Yes | No (works for continuing tasks) |
| Bootstraps? | No | Yes |
| Convergence | Converges within the sample | Converges to the MDP value in the tabular case |
A must-know interview question — "What's wrong with MC and TD?"
- MC: high variance — a single trajectory mixes "the policy is good" with "we got lucky," and there's no way to separate the two;
- TD: biased — $V(s_{t+1})$ is wrong early on, and bootstrapping propagates that error;
- The compromise is TD(λ)/GAE: multi-step returns let you slide smoothly between the two (see the GAE section in policy gradient methods).
4. SARSA and Q-Learning: The Divide Between On-Policy and Off-Policy
Apply TD ideas to action values and you get two classic algorithms. They differ in exactly one place in the update formula, yet that single difference marks the most important conceptual divide in RL.
1. Q-Learning (Off-Policy): Learn the "Optimal" While Behaving "Suboptimally"
$$ Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left[ r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a') - Q(s_t, a_t) \right] $$
The key is $\max_{a'}$: the update uses the Q of the best action at the next state, regardless of which action was actually taken. So:
- Behavior policy: ε-greedy — handles interacting with the environment and generating data;
- Target policy: greedy — defines "the optimal policy we want to learn."
The two are allowed to differ → this is off-policy learning.
2. SARSA (On-Policy): Learn the Policy I'm Actually Following
The only difference: replace $\max_{a'} Q(s_{t+1}, a')$ with $Q(s_{t+1}, a_{t+1})$ — the value of the action actually taken next. SARSA learns the value of the current policy including its exploration → this is on-policy.
| Dimension | SARSA | Q-learning |
|---|---|---|
| Full name | State-Action-Reward-State-Action | Not an acronym — just a name |
| Update uses | Q of the actual action $a_{t+1}$ | Q of the best action $\max_{a'}$ |
| On/off-policy | On-policy | Off-policy |
| Sensitivity to exploration | Cliff-averse: bakes the cost of ε-exploration into the value | Blind to exploration: learns the purely optimal policy |
| Converges to | The value of the ε-greedy policy | The value of the optimal policy |
3. The Classic Cliff Walking Story: SARSA Is "Timid" but Safer
Sutton & Barto's cliff walking example: to get from start to goal, the shortest route hugs the cliff edge — but one slip and you fall off.
- Q-learning learns the value of "take the optimal step every time," so it hugs the cliff — the optimal policy is the shortest route. But during training, ε-greedy occasionally steps off the cliff → highly volatile performance.
- SARSA bakes "you might fall off while exploring" into the value, so it learns to keep a respectful distance from the cliff → much steadier training.
Engineering takeaway
In systems where you must control risk during training (real robots, trading capital), the on-policy "caution" is a feature. When you learn a final policy offline (train first, deploy later), the off-policy "boldness" fits better. Neither is universally right — what matters is whether the algorithm matches how the policy will be deployed.
4. Tabular Q-Learning: Pseudocode
python
# Tabular Q-learning
def q_learning(env, episodes, alpha=0.1, gamma=0.99, eps=0.1):
Q = defaultdict(lambda: zeros(n_actions)) # initialize Q to all zeros
for _ in range(episodes):
s = env.reset()
done = False
while not done:
a = eps_greedy(Q, s, eps) # behavior policy: ε-greedy
s_next, r, done = env.step(a)
# update rule (off-policy, uses max)
td_target = r + gamma * max(Q[s_next]) if not done else r
Q[s][a] += alpha * (td_target - Q[s][a])
s = s_next
return QImplementation pitfalls in tabular Q-learning
- Handling
done: a terminal state has no "next step," so $td_target = r$ (you must not add $\gamma Q(s_{next})$). Miss this and terminal values get over- or underestimated — the most common beginner bug;- Continuous states must be discretized (binned) first, or the table explodes;
- α and ε must be tuned together: aggressive exploration calls for a smaller α, otherwise your estimates jitter.
5. DQN: Replace the Table with a Neural Network
1. The Problem: A Table Can't Hold the Real World
An Atari game feeds in 210×160 pixel frames — the state space is astronomically large, so no table can exist. The deep Q-network (DQN) instead approximates the Q-function with a neural network $Q_\theta(s,a)$ (Mnih et al., 2015, Nature).
Network output: given $s$, it produces a vector of Q-values over all actions, $[Q_\theta(s,a_1), \dots, Q_\theta(s,a_K)]$. The loss function literally says "make Q satisfy the Bellman equation":
$$ L(\theta) = \mathbb{E}{(s,a,r,s') \sim \mathcal{D}} \left[ \left( r + \gamma \max Q_{\bar\theta}(s', a') - Q_\theta(s,a) \right)^2 \right] $$
Here $Q_{\bar\theta}$ is the target network — its parameters are periodically copied from $\theta$. The term in brackets is the TD error; the objective is simply to minimize its square.
2. Two Engineering Tricks: Why DQN Diverges Without Them
Trick one: experience replay
Store $(s,a,r,s')$ in a replay buffer and sample random minibatches from it for training. This solves two problems at once:
| Problem | How replay fixes it |
|---|---|
| Samples are strongly correlated (consecutive steps) | Random sampling breaks the temporal correlation → data looks closer to i.i.d., so SGD behaves |
| Samples are wasted (used once, then discarded) | Each experience can be replayed many times → better data efficiency |
Trick two: the target network
DQN's regression target $r + \gamma \max Q$ depends on the very network being updated. Compute that target with θ itself and the target moves at every step → the gradient chases a moving target → oscillation, or outright divergence. The fix: freeze a copy $\bar\theta$ and copy θ into it only every N steps. The target now moves once every N steps instead of every step, and training stabilizes.
Remember DQN's motivation in one sentence
"The regression target contains the model itself" (bootstrapping) is the root of DQN's instability. Replay fixes sample correlation; the target network fixes the moving target. From then on, these two tricks became standard infrastructure for deep RL — nearly every modern algorithm (SAC and TD3 included) carries them.
3. DQN's Preprocessing and Architecture
The classic Atari setup: grayscale → crop to 84×84 → stack the most recent 4 frames into an 84×84×4 input (the history supplies the "velocity" information, patching over the Markov property) → a convolutional network → Q-values for 18 actions. See Atari and Video Games for the full case study.
6. The DQN Family: Seven Improvements and Rainbow
1. Double DQN: Curing Overestimation
Q-learning's $\max$ naturally overestimates values (the max operator pushes noise upward). Double DQN (van Hasselt et al., 2016) splits "choosing the action" and "evaluating it" across two networks:
$$ r + \gamma , Q_{\bar\theta}\left(s', \arg\max_{a'} Q_\theta(s', a')\right) $$
The intuition: the online network picks "which action is best," and the target network answers "what is it worth." The two estimates' noise partially cancels, and overestimation drops markedly.
2. Dueling DQN: Decoupling Value and Advantage
Dueling DQN (Wang et al., 2016) splits the output into two branches:
$$ Q(s,a) = V(s) + A(s,a) - \overline{A}(s) $$
- $V(s)$: how good the state itself is (the part independent of the action);
- $A(s,a)$: how much better this action is than average — the advantage.
The intuition: in some games, "how good is the situation overall" matters far more than "which exact action to take" (when the ball is about to drop, running left or right barely matters). Dueling lets the network focus on the information that actually differs between actions, so it learns faster and more stably.
3. Prioritized Replay: Not All Transitions Are Equal
Plain replay samples uniformly. But transitions with large TD errors carry the most information (they're the ones the model predicts most wrongly). Prioritized Replay (Schaul et al., 2016) samples in proportion to $|\delta_t|$ and compensates with importance-sampling weights (so the frequently sampled transitions don't overfit).
4. C51 (Distributional RL): Learn the Distribution, Not the Mean
C51 (Bellemare et al., 2017) doesn't learn the expectation $Q(s,a)$ — it learns the entire distribution of the return, represented as a categorical distribution over 51 fixed atoms. The distribution carries far richer information, can characterize risk, and delivers outstanding results on Atari.
5. NoisyNet: Exploration Built into the Network
As mentioned in Exploration and Exploitation, NoisyNet adds learnable noise to the layers, replacing ε-greedy's random exploration. See the exploration discussion on the multi-armed bandits page.
6. Rainbow: The Summary Table
Rainbow (Hessel et al., 2018) bundles the seven improvements and validates each one with ablations:
| Improvement | Problem solved | The mechanism in one line |
|---|---|---|
| Double DQN | Value overestimation | Action selection decoupled from evaluation |
| Prioritized Replay | Sample utilization | Sample weighted by TD error |
| Dueling | Action redundancy | Learn V and A separately |
| Multi-step returns | Bootstrapping bias | Bootstrap after n steps (like TD(λ)) |
| Distributional Q (C51) | Learns only the mean | Learn the return distribution |
| NoisyNet | Unintelligent exploration | Noise inside the network |
| Parameter updates | Unstable learning | Cyclic learning rates (instead of fixed α) |
Engineering takeaway
You don't need to implement Rainbow from scratch. For most real projects (continuous control especially), reach for SAC/TD3 first (see the Actor-Critic family); climb the Rainbow family only when the action space is discrete and you need to squeeze out every last drop of performance.
7. The Limitations of Value-Based Learning
| Limitation | Cause | Consequence |
|---|---|---|
| Paralyzed in continuous action spaces | Policy = argmax Q, and max can't be computed directly in continuous spaces | Value-based learning has largely exited continuous control (DQN can't drive robots) |
| Value overestimation | Statistical bias of the max operator | Double-style fixes help, but only alleviate |
| Sensitive to reward scaling | Q values scale with reward magnitude | Needs reward scaling and similar tricks |
| No convergence guarantee (deep version) | Bootstrapping + nonlinear approximation | Training is unstable and needs stacks of tricks |
When NOT to use value-based learning
- Continuous actions → use policy gradients / Actor-Critic (SAC, PPO);
- The policy must be explicitly stochastic (poker, games of strategy) → policy gradients do this natively;
- Extremely sparse rewards → value-based learning needs extra exploration machinery (RND and friends). The theoretical significance of value-based learning is no smaller than its practical one: it is the vehicle for understanding TD learning, bootstrapping, and off-policy learning — foundational concepts shared by all of RL.
8. Where to Practice
- Want to run tabular Q-learning yourself → Progressive Tutorial: Getting Three Versions of Gymnasium Running (version one is complete tabular Q-learning code);
- Want to read the DQN papers in the original → Classic Paper Deep Dives (close readings of Watkins' Q-learning and Mnih's DQN, one paper at a time);
- For the math (TD convergence proofs, contraction mappings of Bellman operators) → Math Basics Quick Reference;
- How value-based learning teams up with a policy network in Actor-Critic → The Actor-Critic Family.
Further Reading
- Markov Decision Process (MDP) — the Bellman equation is the starting point of every algorithm on this page
- The Actor-Critic Family — in actor-critic, the value network steps back into the "judge" role
- Atari and Video Games — DQN and Rainbow in practice, with the seven improvements validated
- Classic Paper Deep Dives — close readings of the original Q-learning and DQN papers
- Math Basics Quick Reference — the math behind expectation, bootstrapping, and convergence
- Progressive Tutorial: Getting Three Versions of Gymnasium Running — hand-write tabular Q-learning and watch the learning curve
References
- Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. Chapters 5–7 (MC/TD/Q-learning/SARSA) and Chapter 11 (off-policy approximation).
- Watkins, C. J. C. H., & Dayan, P. (1992). Q-learning. Machine Learning, 8(3-4), 279-292. The original Q-learning paper, with its convergence proof.
- Mnih, V., Kavukcuoglu, K., Silver, D., et al. (2015). Human-level control through deep reinforcement learning. Nature, 518, 529-533. The Nature paper that introduced DQN.
- van Hasselt, H., Guez, A., & Silver, D. (2016). Deep Reinforcement Learning with Double Q-learning. AAAI. arXiv:1509.06461
- Wang, Z., Schaul, T., Hessel, M., et al. (2016). Dueling Network Architectures for Deep Reinforcement Learning. ICML. arXiv:1511.06581
- Schaul, T., Quan, J., Antonoglou, I., & Silver, D. (2016). Prioritized Experience Replay. ICLR. arXiv:1511.05952
- Hessel, M., Modayil, J., van Hasselt, H., et al. (2018). Rainbow: Combining Improvements in Deep Reinforcement Learning. AAAI. arXiv:1710.02298