Bonus: Learn the model, then plan

Using every move

Step 3's Q-learning made hundreds of thousands of moves, and used each one once: a small nudge to one $Q(s, a)$, then it was gone. Step 7 did better on the cart-pole by keeping its data and learning a model. The same works on the grid: learn $P$ and $R$ from the moves, then plan with step 2's value iteration.

A model from counts

Let $N(s, a, s')$ count how often action $a$ in state $s$ led to $s'$, and $n(s, a) = \sum_{s'} N(s, a, s')$ how often $a$ was tried in $s$. The maximum-likelihood model, the one that makes the moves seen most probable, is

With 10,000 moves over 576 states and 8 actions, each pair is tried about twice, so the model is rough. A pair never tried has no data. Treat it as a bump: the arm stays put and earns −10. That's pessimistic, so the plan steers clear of what it doesn't know. The goal ends the task, as in step 1: make it absorbing, $\hat P(\text{goal} \mid \text{goal}, a) = 1$ with reward 0.

Your task

Write estimate_model(transitions, n_states, n_actions, goal). transitions is a list of moves (s, a, r, s2); return (P, R), of shapes (S, A, S) and (S, A). zip(*transitions) splits the list into columns, and np.add.at(counts, (s, a, s2), 1.0) counts them all at once, repeats included.

The program makes 10,000 moves with random actions. After 2,500, 5,000 and 10,000 of them it plans on your model, and also runs step 3's Q-learning update over the same moves, each once. The Plots tab compares how often each greedy policy reaches the goal. Planning on the model must reach it from 45 of 50 random starts at least 90 % of the time, and the arm then drives a greedy episode from its start.