# Lab 1: a gridworld, a few policies, and the return

You will build the smallest complete RL setup: an **environment** with `reset()` and `step(a)`, some **policies**, a loop that plays an **episode**, and a Monte Carlo estimate of how good a policy is. No learning yet: that starts in Chapter 2. numpy only.

This is the same world as the demo in Chapter 1:

```
    col:  0 1 2 3 4 5 6
    row 0 . . . . . . .      the long, safe way round (10 steps)
    row 1 . # # # # # .
    row 2 S . . . . . G      the bridge (6 steps)
    row 3 . P P P P P .      pits under the bridge

    G: +1, episode ends     P: -1, episode ends     #: wall (you stay put)
    any other move: step_reward (default 0)
    slip: with probability `slip` your action is replaced by a perpendicular one
```

## How to run

```bash
python -m pytest -q                 # all tests fail until you fill in the TODOs
python -m pytest -q -k discounted   # just Task 1
python run.py                       # once everything passes
RL_SOLUTIONS=1 python -m pytest -q  # check the reference solution (all pass)
```

## Tasks (all in `gridworld.py`)

1. **`discounted_return(rewards, gamma)`**. $G_0 = r_0 + \gamma r_1 + \gamma^2 r_2 + \dots$ Tests: `-k discounted`.
2. **`GridWorld.reset()` and `GridWorld.step(a)`**. The environment. Slip first, then move, then reward. Use `self.rng` for every random number so that runs are reproducible. Tests: `-k "reset or step"`.
3. **`random_policy(state, rng)` and `safe_policy(state, rng)`**. `bridge_policy` is written for you as an example. Your `safe_policy` must say what to do in every state, not just on its favorite path, because slipping can put you anywhere. Tests: `-k policy`.
4. **`run_episode(env, policy, gamma, max_steps, rng)`**. The agent–environment loop from the chapter, in eight lines. Returns `(G, rewards)`. Tests: `-k run_episode`.
5. **`estimate_return(env, policy, gamma, n_episodes, max_steps, seed)`**. Average the return over many episodes, and report the standard error. Tests: `-k estimate`.

All 14 tests pass in about a second.

## What you should see

`python run.py` prints one episode of each policy, then a table like:

```
slip 0.0:  random -0.435 ± 0.007   bridge +0.590 ± 0.000   safe +0.387 ± 0.000
slip 0.2:  random -0.439 ± 0.007   bridge -0.037 ± 0.014   safe +0.261 ± 0.006
```

and saves `returns_vs_slip.png`: the average return of both hand-written policies as the slip probability goes from 0 to 0.4. On a dry floor the bridge wins ($0.9^5 = 0.590$ against $0.9^9 = 0.387$). It loses as soon as the slip probability passes about **0.07** (the exact value is 0.068). Your crossover will differ slightly from run to run because it is estimated from samples.

Things to notice (they come back in the chapter's exercises):

- The random policy's average return is the same at slip 0 and slip 0.2. Why? (A uniformly random action, sent through a slippery floor, is still uniformly random.)
- The best route depends on the environment (the slip), on the discount $\gamma$, and on the step reward, not only on the map. Try `GAMMA = 0.99` at the top of `run.py`: the long way round costs almost nothing, so the crossover moves down to about 0.008.
- The standard errors tell you how many episodes you need. Halving the error costs four times as many episodes.

## Going further (optional)

- Add `step_reward=-0.04` to the `GridWorld(...)` calls in `run.py` and rerun. Which route does the penalty favour, and why?
- Set `GAMMA = 1.0`. Now a long route costs nothing at all. Predict the plot before you run it (and why the script then reports no crossover).
- Chapter 3 will compute these averages *exactly*, without sampling, by solving a linear system. The numbers in `test_estimate_return_matches_exact_values` come from that.