# Lab 3: Markov decision processes as arrays

In this lab you turn the chapter's math into about 25 lines of numpy. You will:

1. write down the slippery gridworld as two arrays, `P[s, a, s']` and `R[s, a]`;
2. collapse it under a policy into a Markov chain `P_pi` and a reward vector `r_pi`;
3. compute `V^pi` two ways: one linear solve, and by iterating the Bellman equation;
4. get `Q^pi` from `V^pi` with one step of lookahead.

Everything is numpy only. The tests run in a few seconds.

## Files

| File | What it is |
|---|---|
| `mdp.py` | **Your file.** Five functions with `# TODO`s. |
| `envs.py` | Helpers you don't need to write: the grid layout, `move()`, `perpendicular()`, the machine MDP from the chapter, policy presets, a Monte Carlo sampler, a pretty-printer. Skim it first. |
| `test_mdp.py` | The tests. |
| `run.py` | Prints and plots the values of three policies, plus the convergence of iterative evaluation. |
| `solutions/mdp.py` | Reference solution. Try first! |

## The gridworld (the same one as in the chapter's demo)

```
row 0:   .  .  .  G      G = goal: +1 on the step that enters it
row 1:   .  #  .  P      P = pit:  -1 on the step that enters it
row 2:   S  .  .  .      # = wall, S = start
```

States are numbered `s = row * 4 + col` (so the start is state 8). Actions are `0 up, 1 right, 2 down, 3 left`. With probability `1 - slip` you move where you meant to; with probability `slip/2` each you slip to one of the two perpendicular directions. Bumping into the wall or the edge leaves you where you were. Every step costs `step_reward` (default `-0.04`). Goal and pit are **absorbing**: once there, you stay forever and collect 0. The wall cell is kept as a dummy absorbing state so that state numbers stay simple; nothing ever enters it.

## Tasks

Do them in order; each test name says which task it checks.

1. **`build_gridworld(slip, step_reward)`** returns `P` with shape `(12, 4, 12)` and `R` with shape `(12, 4)`. Watch out for two outcomes that land on the same cell (two bumps): add their probabilities.
2. **`policy_matrices(P, R, pi)`** returns `P_pi[s, s'] = Σ_a π(a|s) P(s'|s,a)` and `r_pi[s] = Σ_a π(a|s) R[s,a]`.
3. **`evaluate_exact(P, R, pi, gamma)`** solves `(I − γ P_pi) V = r_pi`. The test checks the machine example you solved by hand in the chapter: `(2, −3, −9)` and `(3, 0.5, −8.5)` at `γ = 0.5`. It also simulates 3,000 episodes and checks that the average return matches `V(start)`. That is the definition `V^π(s) = E[G_t | s_t = s]` checked numerically.
4. **`evaluate_iterative(P, R, pi, gamma, tol, max_iters)`** starts at `V = 0` and repeats `V ← r_pi + γ P_pi V` until nothing changes by more than `tol`. It must agree with Task 3.
5. **`q_from_v(P, R, V, gamma)`** returns `Q[s, a] = R[s, a] + γ Σ_s' P[s, a, s'] V[s']`. The tests check `Σ_a π(a|s) Q(s,a) = V(s)`, and that switching the start state to the action with the largest Q improves the policy (a preview of Chapter 4).

## Run

```bash
python -m pytest -q                    # your code (fails with NotImplementedError until you fill in the TODOs)
RL_SOLUTIONS=1 python -m pytest -q     # the reference solution: all 15 pass
python run.py                          # prints value grids, saves values.png
```

## What you should see

`run.py` prints a value grid for each policy (γ = 0.9, slip = 0.2, step reward −0.04) and ends with a line like

```
V(start): uniform random -0.410, shortest path +0.239, safe detour +0.346 | iterative eval (random policy) needed 142 sweeps | ...
```

These are the same numbers the chapter's demo shows for the same settings. `values.png` has three value heatmaps and a log-scale plot of the error of iterative evaluation. The error falls along a straight line at or below the `γ^k` bound: that is geometric convergence, which Chapter 4 proves.

## Going further (optional)

- Evaluate all 8 deterministic machine policies (`itertools.product([0, 1], repeat=3)`) at γ = 0.5 and γ = 0.9. Which is best in each case? This is Exercise 3.6 in the chapter.
- Turn the random policy's slip up and down. Its values don't change at all. Why? (Hint: what does slipping do to a uniformly random action?)
- Set `step_reward=+0.1` and evaluate a policy that never reaches a terminal state. Compare its values with `0.1 / (1 − γ)`.