Learning by trial and error: Q-learning

No map, no planner, nobody telling it the answer. Just a robot that tries things, gets points, and slowly writes down which moves were worth it.

Going deeper: everything below is the full lesson: the idea built from nothing, a demo, your homework, and a challenge away from the screen.

1. The problem

Here is the maze from lesson07_trial_error.py. S is the start, G the goal, # a wall. Coordinates work just like Lesson 1: (x, y), with y growing downwards.

#######
#S..#.#      S is at (1, 1)
#.#.#.#      G is at (5, 4)
#.#...#
#...#G#
#######

You can see the shortest way is 7 steps (E, E, S, S, E, E, S). The robot can't see this picture. It only knows the square it's on. If it moves into a wall, safe_move from Lesson 1 keeps it where it was, and it has wasted a step.

Obvious idea 1: wander randomly until you hit G. It works, eventually. With random moves, the robot's very first attempt in our code took 58 steps. The second took 101. And it never gets better, because it remembers nothing.

Obvious idea 2: remember the whole route that worked, and repeat it. Better, but the first route that worked was a 58-step mess full of bumps into walls. Repeating a bad route doesn't make it good. We need to remember something smaller and smarter than "the route".

2. First principles

Step 1: give every move a score

Instead of remembering a route, keep a table. For each square and each of the 4 moves, store one number: the Q-value. At the start, everything is 0 because the robot knows nothing.

Q[((5, 3), "S")] = 0     # from (5, 3), moving South: worth 0 so far
Q[((5, 3), "W")] = 0
...

In Python that's a dictionary whose keys are (square, move) pairs. Missing keys count as 0, so we only store what we've learned.

Step 2: rewards say what we want

We never tell the robot the route. We only say what's good and bad:

• every step costs −1 (so long, wandering routes score badly);
• reaching G gives +10, and the episode ends.

A 7-step route scores −1 × 6 + 10 = +4. A 58-step route scores −57 + 10 = −47. So "get the most points" and "find the shortest route" are now the same goal. Choosing rewards like this is a real skill: you describe what you want, and let learning work out how.

Step 3: learn backwards from the goal (the simple version)

Let's pretend the learning rate is 1 for a moment (we just overwrite the old value). The rule is:

new Q = reward                                    if this move ended the episode
new Q = reward + γ × (best Q at the next square)  otherwise

"Best Q at the next square" is the robot's current guess of how well things go from there. Watch it spread backwards along the bottom-right corridor, with γ = 0.95:

From (5, 3) move S reaches G:   Q = 10                       (done, so just the reward)
From (4, 3) move E to (5, 3):   Q = −1 + 0.95 × 10   = 8.5
From (3, 3) move E to (4, 3):   Q = −1 + 0.95 × 8.5  = 7.075
From (3, 2) move S to (3, 3):   Q = −1 + 0.95 × 7.075 ≈ 5.72

Each square near the goal learns "this move is good", and then the square before it learns from that. Good news travels backwards, one square per visit. The robot never needed a map. It just needed to visit the squares enough times.

Step 4: don't trust one experience too much (learning rate α)

Overwriting is risky. Early guesses are often wrong, and later we'll add random moves. So instead we move the old value part of the way towards the new target:

Q[(square, move)] += α × (target − Q[(square, move)])

With α = 0.5, this means "go halfway". Here's the exact example that check.py uses. The robot is at (1, 1), moves E to (2, 1), gets −1. It already believes Q[((2, 1), "S")] = 4, and every other Q is 0. Use γ = 0.9:

best Q at (2, 1)   = max(0, 4, 0, 0) = 4
target             = −1 + 0.9 × 4    = 2.6
old Q[(1,1), E]    = 0
new Q[(1,1), E]    = 0 + 0.5 × (2.6 − 0) = 1.3

And the goal move, visited three times with α = 0.5: 0 → 5 → 7.5 → 8.75. It creeps towards 10 and never jumps there from one lucky try.

Step 5: explore, or you'll get stuck with your first idea

If the robot always picks its best-scoring move (exploit), it may lock onto the first route that worked, even if it's the long one down the left side. So sometimes it must try a random move (explore). We use a number ε (epsilon) = 0.2:

roll a random number between 0 and 1
if it's below 0.2:  pick a random move        (explore, 20% of the time)
otherwise:          pick the best-scoring move (exploit, 80% of the time)

This is called ε-greedy. It's the same choice you make picking food: your favourite (exploit) or something new that might be even better (explore).

When all the Q-values for a square are tied (like at the start, when they're all 0), we pick the first move in the order "NSEW". That rule matters: it makes the program behave the same every time, so the checker can test it.

Step 6: put it all together

repeat for 300 episodes:
    stand on S
    until you reach G (or 200 steps pass):
        choose a move (ε-greedy)
        do it with safe_move, see where you land
        reward = +10 if you landed on G, else −1
        update Q for (square, move)
        move to the new square

After training, to use what it learned, the robot turns exploring off and just follows the best move from every square. That's the "greedy path".

3. Play with it

4. Homework

Open homework/lesson07_trial_error.py. The maze, ACTIONS = "NSEW" and find_char are written for you. It imports safe_move from your Lesson 1 file, so Lesson 1 must be finished. Write these five functions, in order. Q is a dictionary with keys like ((1, 1), "E").

4.1 best_action(Q, pos)

Return the move (one letter) with the highest Q-value at pos. Missing values count as 0. On a tie, return the one that comes first in "NSEW".

Example: best_action({}, (1, 1)) → "N" (all zeros, so the first). best_action({((1, 1), "E"): 2.0}, (1, 1)) → "E".

4.2 choose_action(Q, pos, epsilon, rng)

ε-greedy. With probability epsilon return rng.choice(ACTIONS), otherwise return best_action(Q, pos).

Example: with epsilon = 0 it always exploits, so choose_action({((1, 1), "W"): 5.0}, (1, 1), 0.0, rng) → "W".

4.3 q_update(Q, pos, action, reward, next_pos, alpha, gamma, done)

The learning rule from Step 4. It changes Q in place and returns nothing.

Worked example (from above): Q = {((2, 1), "S"): 4.0}, then q_update(Q, (1, 1), "E", -1.0, (2, 1), 0.5, 0.9, False) leaves Q[((1, 1), "E")] == 1.3.

4.4 q_learn(room, start, goal, episodes=300, ...)

Run the whole training loop from Step 6. Return two things: the Q dictionary and a list with the number of steps each episode took.

4.5 greedy_path(Q, room, start, goal, max_steps=100)

Use what was learned, with no exploring: from start, keep taking best_action until you reach goal. Return every square visited, including the start.

Run it

cd homework
python3 lesson07_trial_error.py

What you should see (this is the real output of the reference solution):

steps in first 5 episodes: [58, 101, 13, 46, 22] | last 5: [9, 9, 9, 11, 10]
#######
#S**#.#
#.#*#.#
#.#***#
#...#G#
#######
learned route length: 7

The * marks show the route the robot learned on its own. Your first-five numbers will match exactly only if you call rng in the same order as described (one rng.random() per choice, then rng.choice only when exploring). If they differ but the route is still 7, your code is probably fine.

Check it

cd ..
python3 check.py 7

A green ✓ means that function passed. A red ✗ comes with a hint. For example:

• ✗ best_action: all zeros: pick the first action, 'N' means your tie-break is wrong (maybe you used >=, so the last tied letter wins).
• ✗ q_update: target = -1 + 0.9 * 4; Q moves halfway there means your target or your α step is off. Work the 1.3 example on paper and compare.

Yellow … means "not written yet". All four green and you'll see 4/4 passed.

Stretch

• Change the step reward from −1 to 0 and run again. Does the robot still find the 7-step route? (Think: if steps are free, why hurry? γ is the only thing left pushing it.)
• Make ε shrink over time: start at 1.0 and multiply it by 0.98 after each episode. Do the last episodes get down to 7?
• Draw your own bigger maze in the MAZE list (keep the walls round the edge) and train on it. How many episodes does it need now?

5. Real-world challenge: be the Q-learner

You'll learn a "maze" with no map, using only rewards, exactly like the robot.

1. Ask someone to draw a secret 4 × 4 grid maze on paper (start in one corner, goal in another, a few walls), and keep it hidden from you.
2. Draw your own empty 4 × 4 grid. This is your Q-table: in each square, leave room for four small numbers (N, S, E, W), all starting at 0.
3. Play an episode. Say a move out loud. Your partner answers only "wall" (you stay put), "step" (−1) or "goal!" (+10). Keep count of your steps.
4. After every move, update the number for that square and move with the simple rule: target = reward + 0.9 × (best number in the square you landed on). To keep the maths easy, use α = 1 (just write the target in).
5. Play 6 to 8 episodes. Mostly pick your best-scoring move, but roll a die before each move: on a 1, pick a random direction (that's ε ≈ 0.17).
6. Record the steps per episode in a little table and draw a quick bar chart.

What to notice: the numbers fill in from the goal backwards, and your episodes get shorter even though you never saw the map. Also notice how annoying the die is when you already "know" the way, and think about when it saved you from a long route. Bonus: swap roles and see if your partner learns faster or slower than you.

6. Your Robo-Helper so far

Let's be honest: this lesson is a side quest. The finished Robo-Helper (Lesson 11) does not use Q-learning to drive around the room. It has a map, so it uses astar_path from Lesson 6, which is faster and always finds the shortest route. That's the right engineering choice. Don't use trial and error when you can plan.

So why learn it? Because there's a whole family of robot skills where nobody can write the map or the rules down. Walking, running, picking up squishy things, balancing. For those, real robotics teams use the same loop you just wrote: try, get a reward, update, repeat. They run it millions of times inside a simulator (a video-game copy of the robot and the world), because a real robot falling over a million times would break. Then they copy what was learned to the real robot. The maths is fancier (a neural network instead of a table, and methods such as PPO instead of plain Q-learning), but the idea is yours now.

What you built: q_learn and greedy_path, a robot that learns MAZE by itself. What comes next uses language instead: in Lesson 8 the robot starts turning words into numbers, the first step towards understanding "put the red block in the bin".

7. Common mistakes

• Wrong tie-break. Using >= instead of >, or max on values only, can return the wrong letter when values are equal. Checker hint: "all zeros: pick the first action, 'N'".
• Creating Q inside the episode loop. Then the robot forgets everything after each attempt and never improves. Checker hint: "episodes should get shorter as the robot learns".
• Looking ahead after the goal. When done is True the target is just the reward. Adding γ × (Q at the goal square) makes the goal look worth more than it is.
• Using Q[(pos, a)] instead of Q.get(...). Unvisited pairs aren't in the dictionary yet, so you'll get a KeyError.
• Exploring when you should exploit. greedy_path must use best_action, never choose_action. Otherwise the route is random each time. Checker hint: "after training, the greedy route should be the shortest: 7 steps".

8. Check yourself

9. Go deeper (optional)

• TensorTonic: the RL ladder: practice problems that climb from discounted rewards (your γ) to the Bellman equation (your q_update) and beyond.
• 30u30 Day 29: PPO: the algorithm many walking robots (and ChatGPT's fine-tuning) are trained with. It's the grown-up cousin of what you just wrote.
• GRPO: reinforcement learning used to train language models to reason, with rewards for correct answers.
• Free robotics courses: where to learn more robotics, at no cost.