# Lab 6: function approximation and DQN

You will build Deep Q-Networks from the pieces up and train it to balance CartPole.
Everything runs on a laptop CPU: the tests take about 15 seconds, a training run about a minute.

## Files

| File | What it is |
|---|---|
| `dqn.py` | **Your file.** Five tasks, each a `# TODO` + `raise NotImplementedError`. |
| `train.py` | The DQN training loop (provided). Read it: each numbered comment is a line of the chapter's pseudocode. |
| `cartpole.py` | CartPole in plain numpy (provided). |
| `test_dqn.py` | Tests, one group per task. |
| `run.py` | Trains DQN on CartPole and saves `dqn_cartpole.png`. |
| `solutions/dqn.py` | Reference solution. Try first, peek later. |

Dependencies: `numpy`, `torch`, `matplotlib`, `pytest`.

## Tasks (in order)

Run the tests for one task at a time: `python -m pytest -q -k task1`, then `-k task2`, and so on.

1. **`linear_td0_update`**: semi-gradient TD(0) with linear features, in numpy.
   The tests use the chapter's hand-worked "hat feature" examples, check that one-hot
   features give tabular TD(0), and reproduce the deadly-triad example: with off-policy
   updates the weight grows like 1.08^100 ≈ 2200, while with on-policy updates it shrinks to 0.
2. **`ReplayBuffer.push` / `ReplayBuffer.sample`**: a circular buffer that overwrites
   the oldest transition when full and samples uniformly from what is stored.
3. **`QNetwork`, `epsilon_by_step`, `select_action`**: an MLP with one output per action,
   a linear ε schedule, and ε-greedy action selection.
4. **`compute_td_targets`, `dqn_loss`**: targets `y = r + γ (1 − done) max_a' Q(s', a'; θ⁻)`
   (and the Double DQN version), computed under `torch.no_grad()`, plus the mean Huber loss.
   The tests use the 3-state worked minibatch from the chapter, and check that the gradient
   is a *semi*-gradient: nothing flows through the target, even when the online and target
   networks are the same object.
5. **`update_target`, `train_step`**: hard and soft (Polyak) target updates, and one full
   gradient step (sample, loss, backward, clip gradient norm, optimizer step).
   The last test trains for 12k steps and checks that the agent balances the pole for
   longer than 60 steps on average (a random policy manages about 22).

When everything passes:

```bash
python -m pytest -q          # all 20 tests
python run.py                # ~1 minute; prints progress, saves dqn_cartpole.png
```

## What you should see

With the default settings (Double DQN, replay buffer of 50k, target network copied every
500 steps, Adam at 5e-4, 50k environment steps, seed 0), the reference solution reaches a
final greedy return of about 430 (the maximum is 500).

- **The evaluation curve is jumpy.** Drops from 500 to about 150 and back are normal for DQN on
  CartPole. This is not a bug: it's what learning without convergence guarantees looks like.
  Try other seeds (`--seed 1`) to see the spread.
- **The loss goes up, then stays flat.** The DQN loss is not a progress meter. As the
  Q-values grow toward their true scale (up to about 1/(1 − γ) = 100) and the targets move,
  the regression errors grow too.

## Break it on purpose

```bash
python run.py --compare     # ~2-3 minutes: full DQN vs. no target network vs. no replay
python run.py --no-target   # or one at a time
python run.py --no-replay
python run.py --no-double
```

On seed 0 the reference gets roughly: full DQN ≈ 430; without a target network, the
Q-values diverge (the loss climbs past 1e8) and the agent never balances the pole for more
than about 10 steps; without replay (a buffer holding only the latest 128 transitions),
it learns something but less reliably (≈ 210). That's the deadly triad,
and DQN's fixes for it, in a real network.

## One subtle detail: time limits are not terminal

CartPole stops after 500 steps even if the pole is still up. `train.py` stores such a
cut-off with `done = 0` so the target keeps bootstrapping: the state was still valuable.
Only a real failure (the pole fell or the cart left the track) is stored as `done = 1`.
As an experiment, change line `terminal = done and env.t < env.max_steps` to
`terminal = done` and see what happens to the best runs.