Q-learning

What it computes

Value iteration needs the model $P$ and $R$. Q-learning learns from experience alone: the agent only tries moves and sees where it lands. It learns the action value $Q(s, a)$, the discounted reward of taking $a$ in $s$ and acting well afterwards, and the greedy policy $\arg\max_a Q(s, a)$ is the answer.

The update

After each move $s \xrightarrow{a} s'$ with reward $r$, nudge $Q(s, a)$ towards the TD target, a one-sample Bellman backup:

At the goal nothing follows, so the target is just $r$. Moves slip, so one sample is noisy; the step size $\alpha$ averages many.

Q = zeros(S, A)
repeat episodes times:
    s = env.reset()
    until done:
        a = random with probability eps, else argmax Q[s]
        s2, r, done = env.step(a)
        target = r if s2 is the goal else r + gamma * max Q[s2]
        Q[s, a] += alpha * (target - Q[s, a])
        s = s2

Exploration

Acting only greedily keeps repeating whatever worked first, so ε-greedy tries a random action a fraction ε of the time. Q-learning is off-policy: its target uses the best next action, not the one it will take, so it learns the greedy policy's values even while exploring. (SARSA bootstraps from the action taken next, and learns the exploring policy's values instead.)

Tools

env.reset(), env.step(a), env.n_states and env.n_actions. env.truncated is True when an episode was cut off at 200 moves: the arm didn't arrive, so that target still bootstraps.

See it in context

Value iteration solves the same grid (8 slipping moves, −1 per move, −10 into an obstacle) with the model.

Your task

Implement q_learning(env, episodes, alpha, gamma, eps), starting from $Q = 0$. The program trains for 8,000 episodes ($\alpha = 0.5$, $\gamma = 0.95$, $\varepsilon = 0.3$), plots the learning curve and drives the arm greedily from its start. The grader replays your moves through the update, checks that about ε of them explore, and needs the greedy policy to reach the goal from 45 of 50 random starts.