# Lab 5: Monte Carlo and TD learning

You will build the four core tabular learners of Chapter 5 and reproduce the
chapter's two classic experiments with your own code:

1. **Prediction** on the 5-state random walk: Monte Carlo vs. TD(0).
2. **Control** on the cliff: SARSA vs. Q-learning.

Everything is numpy. The tests run in about 2 seconds; `run.py` in about 10.

## Files

| File | What it is |
|---|---|
| `td.py` | **Your file.** Five tasks marked `TODO`. |
| `envs.py` | The random walk, the cliff, and helpers (`generate_episode`, `train`, `greedy_path`, ...). Complete; read it once. |
| `test_td.py` | The tests. |
| `run.py` | Runs both experiments with your code and saves `td_learning.png`. |
| `solutions/td.py` | Reference solution. Try not to peek. |

## Tasks (in order)

Run the tests for one task at a time with `-k`.

| Task | Function(s) | Chapter section | Test with |
|---|---|---|---|
| 1 | `mc_update`: every-visit constant-α Monte Carlo | Monte Carlo: average what actually happened | `pytest -q -k mc_update` |
| 2 | `td0_update`: TD(0), online | TD(0): learn a guess from a guess | `pytest -q -k td0` |
| 3 | `epsilon_greedy` with random tie-breaking | From prediction to control | `pytest -q -k epsilon_greedy` |
| 4 | `sarsa_target`, `q_learning_target`, `expected_sarsa_target` | SARSA / Q-learning / Expected SARSA | `pytest -q -k target` |
| 5 | `sarsa_episode`, `q_learning_episode` | SARSA / Q-learning | `pytest -q -k control` |

The hand-checkable tests use the same numbers as the chapter: the
two random-walk episodes in the TD(0) section, and Exercise 5.1
(V = [1, 2, 0], α = 0.5, γ = 0.9). If a test fails, do that exercise on
paper first and compare your numbers line by line.

Tips:

- In Task 1, compute all returns with one backward pass (`G = r + gamma * G`),
  then update forward.
- In Task 2, use `0` in place of `V[s_next]` when `done` is true (`s_next` is `None` there).
- In Task 5, the only structural difference between the two loops is *when* the
  next action is chosen. SARSA chooses `a'` before its update, because its
  target needs it. Q-learning doesn't need it.

## Running

```bash
python -m pytest -q                  # fails until you fill in the TODOs
RL_SOLUTIONS=1 python -m pytest -q   # the reference solution: all pass
python run.py                        # your code: prints greedy paths, saves td_learning.png
```

## What you should see

`run.py` prints roughly:

```text
SARSA greedy path (last run):          Q-learning greedy path (last run):
. * * * * * * * * * * .                . . . . . . . . . . . .
* * . . . . . . . . * .                . . . . . . . . . . . .
* . . . . . . . . . * *                * * * * * * * * * * * *
S C C C C C C C C C C G                S C C C C C C C C C C G

RMS error after 100 episodes: TD α=0.05: 0.036, ..., MC α=0.02: 0.085, ...
Cliff, mean return over the last 100 episodes: SARSA -24.9, Q-learning -49.0
```

(The exact SARSA detour varies from run to run.)

- **Left panel.** TD(0) reaches a lower error than Monte Carlo at every step
  size shown, and gets there faster. Large step sizes learn fast but level off
  at a higher error floor: they never stop chasing the noise of the latest episode.
- **Right panel.** SARSA earns about −25 per episode while exploring; Q-learning
  only about −50, even though Q-learning's greedy path is the optimal 13-step
  one. That is the whole lesson of the cliff: Q-learning learns the values of the
  greedy policy, but the agent still acts ε-greedily, and an ε-greedy agent on
  the cliff edge falls off.

## Going further (optional)

- Add `expected_sarsa_episode` (copy your Q-learning loop, swap the target) and
  add it to `run.py`. Try α = 1.0 for all three methods. Which one survives?
- Make ε decay over episodes (for example ε = 0.1 / (1 + k / 100)). Does SARSA's
  path move toward the cliff edge?
- Implement Double Q-learning (two tables, one picks the argmax, the other
  evaluates it) and compare it with Q-learning on a problem with noisy rewards.