# Lab 4: Dynamic programming

Companion to [Chapter 4: Bellman equations and dynamic programming](https://learn.xhelio.ai/rl/learn/04-dynamic-programming/).

You will write the three classic dynamic-programming algorithms (policy evaluation, policy iteration, value iteration) in about 40 lines of numpy. Then you'll use them to solve the slippery FrozenLake exactly. You get no simulator and no sampling: you are given the full model `P`, `R` and you compute.

## Files

| File | What it is |
|---|---|
| `dp.py` | **Your file.** Five functions with `# TODO`s. |
| `envs.py` | Provided: MDP builders (`make_corridor`, `make_gridworld`, `make_frozen_lake`), policy helpers, plotting. Read its docstring once. |
| `test_dp.py` | Tests, grouped by task. |
| `run.py` | Solves 8×8 FrozenLake and saves `dp_frozenlake.png`. |
| `solutions/dp.py` | Reference solution. Try not to peek until you've had a go. |

## Conventions (same as Chapter 3)

- `P[s, a, s2]` is the probability of moving to `s2` after action `a` in state `s`, shape `(S, A, S)`.
- `R[s, a]` is the expected reward, shape `(S, A)`.
- A policy is an `(S, A)` array of probabilities. A deterministic policy is one-hot.
- Terminal states are absorbing with reward 0, so their value is 0.
- Corridor actions: `0 = left`, `1 = right`. Grid actions: `0 = up, 1 = right, 2 = down, 3 = left`.

## Tasks (do them in order)

1. **`q_from_v(P, R, V, gamma)`**: the one-step lookahead $Q(s,a) = r(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V(s')$. One line. Every other task uses it.
   `python -m pytest -q -k task1`
2. **`policy_evaluation(P, R, policy, gamma)`**: iterative policy evaluation with synchronous sweeps. Its tests check the chapter's hand-computed corridor values (0.5, 0.45, 0.405) and compare with Chapter 3's linear solve.
   `python -m pytest -q -k task2`
3. **`greedy_policy(P, R, V, gamma)`**: policy improvement, i.e. argmax of the lookahead. Ties go to the lowest index.
   `python -m pytest -q -k task3`
4. **`value_iteration(P, R, gamma)`**: also return the list of per-sweep max changes. The tests check the chapter's table `[1.0, 0.9, 0.31, 0.0]` and that each change is at most γ times the previous one (the contraction property).
   `python -m pytest -q -k task4`
5. **`policy_iteration(P, R, gamma)`**: evaluate, improve, repeat. The test checks the chapter's sequence LLL → LLR → LRR → RRR.
   `python -m pytest -q -k task5`

The last test, `test_all_tasks_beat_brute_force`, evaluates all 256 deterministic policies of a tiny slippery grid. It checks that your $V^*$ equals their elementwise maximum, so a single policy is best in every state at once.

## Run

```bash
python -m pytest -q                  # your code (fails until the TODOs are done)
RL_SOLUTIONS=1 python -m pytest -q   # reference solution (all pass)
python run.py                        # needs your dp.py to be complete
```

## What you should see

`run.py` prints something like

```
FrozenLake 8x8, γ=0.99: V*(start)=0.415; value iteration 662 sweeps (greedy policy optimal from sweep 127); policy iteration 10 evaluations (3519 evaluation sweeps). Saved dp_frozenlake.png
```

The plot has three panels:

- **Left:** value iteration's max change per sweep on a log axis, for γ = 0.5, 0.9, 0.99. Each curve settles into a straight line (geometric decay), and it is never above its dashed bound δ₁γ^(k−1). The decay is often *faster* than the bound, because falling into a hole ends the episode, which shrinks the effective horizon.
- **Middle:** $V^*$ and the optimal policy. Look at the arrows next to holes. On slippery ice the agent often aims *away* from the hole: it would rather slip sideways along a safe row than risk sliding in.
- **Right:** the greedy policy becomes optimal long before the values converge.

## Going further (optional)

- Make `policy_evaluation` in place (Gauss–Seidel: overwrite `V[s]` as you go). Count the sweeps on 8×8 FrozenLake and compare.
- **Modified policy iteration:** evaluate with only `m` sweeps per improvement. Plot total sweeps against `m` for m = 1 (value iteration), 2, 5, 20, ∞ (policy iteration).
- Time value iteration on a 30×30 random grid, then 60×60. The cost of one sweep grows like (number of states) × (number of actions) × (successors per action). This is a small taste of the curse of dimensionality.