Learning from trial and error

Without the model

Value iteration read $P$ and $R$. A real robot doesn't have them: it can only try a move and see what happens. env = rl.grid_env() is the same grid as an environment. env.reset() puts the arm in a random free cell and returns its state; env.step(a) makes one move and returns (s2, r, done), the new state, the reward and whether the episode is over. It is over at the goal, or after 200 moves, and then env.truncated is True too.

Q-learning

Q-learning learns the action values $Q(s, a)$ from those moves. After each move from $s$ with action $a$, reward $r$ and new state $s'$, it nudges $Q(s, a)$ towards the TD target $y$ (TD for temporal difference):

That's step 2's backup with the sum over $s'$ replaced by the one $s'$ that happened; the learning rate $\alpha$ averages over many tries. At the goal nothing follows, so $y = r$. A cut-off episode is different: the arm only ran out of time, and $s'$ still has a future, so keep the $\gamma \max$ term.

Exploring

Always taking the best-looking action, $\arg\max_a Q(s, a)$, repeats whatever worked first and never finds anything better. ε-greedy exploration takes a random action with probability $\varepsilon$ and the greedy one otherwise.

Your task

1. Write epsilon_greedy(Q, s, eps), using np.random (the program seeds it).
2. Write td_update(Q, s, a, r, s2, terminal, alpha, gamma), changing Q[s, a] in place.
3. Write run_episode(env, Q, alpha, gamma, eps): reset, then choose, step and update until done, and return the total reward. Pass terminal = done and not env.truncated.

The program trains for 8,000 episodes ($\alpha = 0.5$, $\gamma = 0.95$, $\varepsilon = 0.3$). The Plots tab shows how often a greedy arm reaches the goal as training goes on, and the Images tab what has been learned so far (dark cells: nothing yet). Acting greedily, the arm must reach the goal from 45 of 50 random starts at least 90 % of the time, then drive there from its own start.