Machine Learning Foundations / Advanced / 03.12
Q-learning: a score for every move
Q-learning gives every move in every place a score, then fixes the scores by trial and error. Build it from scratch in plain Python on a tiny grid.
13 min readFree
Where we left off
Last time you learned that a reinforcement learning agent tries things and gets a score. But how does it remember which move was good? Q-learning is the classic answer: it writes a score for every move in every place, then corrects those scores a little after every step.
Picture a new city where you are learning the best way to walk to work. At each corner you could turn left, turn right or go straight. After each walk you jot a number on a card for that corner and that turn: a high number if it led to a quick trip, a low one if it led to a muddy shortcut. After a few weeks your cards tell you what to do at every corner.
That pile of cards is a Q-table. Wikipedia calls Q-learning 'a reinforcement learning algorithm that trains an agent to assign values to its possible actions based on its current state, without requiring a model of the environment.' The 'Q' stands for quality: the expected reward of an action taken in a given state.
A quick recap from the last lesson, in two lines. The agent looks at the state, picks an action and gets a reward. It balances trying new things (exploring) with using what it knows (exploiting), and it counts later rewards a bit less, using a discount.
Key words
- State
- Where the agent is right now. In our example, which square of the grid it stands on.
- Action
- One thing it can do from there: up, down, left or right.
- Q-value
- A score for one action in one state: how good is it to do this here, counting the rewards that should follow?
- Q-table
- A grid of Q-values: one row for every state, one column for every action. Hugging Face calls it 'the memory or cheat sheet' of the Q-function.
- Learning rate (alpha)
- How far each update moves the score. Small steps learn slowly and calmly. Big steps learn fast and jump around.
- Discount (gamma)
- How much a reward one step later is worth compared with one now. A number from 0 to 1.
- Epsilon
- The small chance of trying a random move instead of the best-known one.
- Episode
- One full try, from the start square until the game ends.
The Q-table: a cheat sheet
Take a tiny world with four squares in a row and two moves, left and right. The Q-table has four rows and two columns, eight numbers in all. At the start it is filled with zeros. Hugging Face says: 'In the beginning, our Q-table is useless since it gives arbitrary values for each state-action pair (most of the time, we initialize the Q-table to 0).'
As the agent plays, the zeros turn into real scores. Hugging Face puts the payoff this way: when training is done, 'we have an optimal Q-function, which means we have optimal Q-table. And if we have an optimal Q-function, we have an optimal policy since we know the best action to take at each state.'
So using a finished table is easy. Look up your row, glance across the scores and take the move with the biggest one. All the hard work is in filling the table in.
Tip
Do not mix up reward and Q-value. Hugging Face spells it out: the reward is the feedback after one action. The value is the expected total reward if you start there and act well afterwards.
The update rule, in plain words
After every single step, the agent fixes one number in the table. It does this with a small recipe. Here it is in words first: new estimate = old estimate + learning rate × (reward + discount × best next value − old estimate).
- 1
1. Take a step
The agent is in a state, picks an action, lands in a new state and gets a reward.
- 2
2. Find the best next score
Look at the new state's row and take its biggest Q-value. This is the best the agent believes it can do from there.
- 3
3. Build a target
Add the reward you just got to the discount times that best next score. This is what the old number should have been, if the agent's current beliefs about the future are right.
- 4
4. Measure the gap
Target minus the old estimate. A positive gap means 'this was better than I thought'. A negative gap means 'worse'.
- 5
5. Nudge
Move the old number towards the target by a fraction of the gap. The learning rate is that fraction.
Read it out loud: s is the state, a the action, r the reward, s' (say 's prime') the new state. The alpha (α) is the learning rate and gamma (γ) is the discount. The 'max over a prime' means 'the biggest Q-value in the new state's row'. Wikipedia writes the same thing as a weighted average of the old value and the new information.
The learning rate has two ends. Wikipedia: a factor of 0 'makes the agent learn nothing', while a factor of 1 'makes the agent consider only the most recent information'. The discount does the same job for the future: a factor of 0 makes the agent 'myopic', which means short-sighted, and one near 1 makes it 'strive for a long-term high reward'. Wikipedia adds that in practice a constant learning rate such as 0.1 is often used.
Let us do one update by hand. The old score is 0. The agent gets a reward of 1 and the best score in the new state is 0.5. We use a learning rate of 0.1 and a discount of 0.9.
# one update by hand
q_old, reward, best_next = 0.0, 1.0, 0.5
alpha, gamma = 0.1, 0.9
q_new = q_old + alpha * (reward + gamma * best_next - q_old)
print(f"target = {reward + gamma * best_next:.2f}")
print(f"new Q = {q_new:.3f}")Output
target = 1.45 new Q = 0.145
The target was 1 + 0.9 × 0.5 = 1.45. The gap from the old score of 0 is 1.45. We move only a tenth of the way, so the new score is 0.145. If this same step happens again, the score creeps closer to the target. That slow creep is the learning.
Notice a neat trick. The agent improves a guess using another guess: the best next score is itself still being learned. Hugging Face calls this bootstrapping. It works because the real rewards keep flowing in, and they slowly pull everything into line.
Trying new things: epsilon-greedy
The agent must also choose which action to take. If it always takes the best-scoring move, it never discovers a better one. So it uses epsilon-greedy, from the last lesson: with a small chance epsilon it tries a random move, and otherwise it takes the best-known one.
Hugging Face notes that the exploring usually shrinks as training goes on: 'we progressively reduce the epsilon value since we will need less and less exploration and more exploitation.' Our example keeps epsilon fixed at 0.1 to stay short.
Off-policy, in one line
Q-learning acts with the epsilon-greedy habit, but it updates its scores as if it always took the best next move. Hugging Face: 'Off-policy: using a different policy for acting (inference) and updating (training).' That is why the formula uses max, not the move the agent really took next.
Episodes and when it settles
Training runs in episodes. One episode starts at the start square and ends when the game does, at a goal or a pit. Wikipedia: 'An episode of the algorithm ends when state S t + 1 is a final or terminal state.' Then a fresh episode begins, with the table kept from before.
Will the scores ever settle on the right answers? For tables on small, well-behaved problems, yes. Wikipedia says Q-learning 'can identify an optimal action-selection policy for any given finite Markov decision process, given infinite exploration time and a partly random policy.' A Markov decision process is the textbook name for this kind of game: states, actions, rewards. The word 'infinite' is the catch. In practice we stop when the table stops changing much.
Start
A table of zeros. The first episodes are close to random wandering.
Middle
Rewards near the goal reach the squares next to it first. Then their neighbours learn, and so on, backwards along the path.
End
The best move in each square stands out. Updates become small, because the targets match the old scores.
Quick check
In the update rule, what does 'max over a prime of Q(s prime, a prime)' mean?
Worked example: a tiny grid world
Now the whole thing in plain Python, with no libraries. The world is a 4 by 4 grid. The agent starts in the top-left square. The bottom-right square is the goal and gives +10. The square at the right edge of the second row is a pit and gives -10. Both end the game. Every other step costs -1, which pushes the agent to hurry. Walking into a wall leaves it where it is and still costs -1.
We train for 1,000 episodes with learning rate 0.1, discount 0.9 and epsilon 0.1. A fixed random seed means you get exactly the numbers below.
The code
Read it top to bottom. First the world and its rules (step), then the empty Q-table, then the loop of episodes. The key line is the one that starts 'Q[state][action] +='. It is the update rule from above, written in code.
import random
random.seed(3)
SIZE = 4
GOAL, PIT = (3, 3), (1, 3)
MOVES = {"up": (-1, 0), "down": (1, 0), "left": (0, -1), "right": (0, 1)}
ACTIONS = list(MOVES)
ARROW = {"up": "^", "down": "v", "left": "<", "right": ">"}
def step(state, action):
r, c = state
dr, dc = MOVES[action]
r, c = min(max(r + dr, 0), SIZE - 1), min(max(c + dc, 0), SIZE - 1)
if (r, c) == GOAL:
return (r, c), 10, True
if (r, c) == PIT:
return (r, c), -10, True
return (r, c), -1, False
Q = {(r, c): {a: 0.0 for a in ACTIONS} for r in range(SIZE) for c in range(SIZE)}
alpha, gamma, epsilon = 0.1, 0.9, 0.1
totals = []
for episode in range(1, 1001):
state, done, total = (0, 0), False, 0
while not done:
if random.random() < epsilon:
action = random.choice(ACTIONS)
else:
action = max(Q[state], key=Q[state].get)
nxt, reward, done = step(state, action)
best_next = 0.0 if done else max(Q[nxt].values())
Q[state][action] += alpha * (reward + gamma * best_next - Q[state][action])
state, total = nxt, total + reward
totals.append(total)
if episode % 100 == 0:
print(f"episodes {episode - 99:4d}-{episode:4d}: average reward {sum(totals[-100:]) / 100:6.2f}")
print()
for r in range(SIZE):
row = ""
for c in range(SIZE):
if (r, c) == GOAL:
row += " G"
elif (r, c) == PIT:
row += " X"
else:
row += " " + ARROW[max(Q[(r, c)], key=Q[(r, c)].get)]
print(row)Output
episodes 1- 100: average reward 0.69 episodes 101- 200: average reward 4.11 episodes 201- 300: average reward 4.10 episodes 301- 400: average reward 4.10 episodes 401- 500: average reward 4.22 episodes 501- 600: average reward 4.01 episodes 601- 700: average reward 3.76 episodes 701- 800: average reward 3.93 episodes 801- 900: average reward 4.49 episodes 901-1000: average reward 3.63 v v v < > > v X > > v v > > > G
Reading the result
The first ten lines show the average reward in each block of 100 episodes. In the first 100 the average is 0.69: the agent mostly stumbles about. By episode 200 it climbs to 4.11, and it stays around 4 for the rest, between 3.63 and 4.49.
Why not higher? The shortest route from start to goal is six moves: five steps at -1, then +10 for the last, so 5 in total. A perfect run would score 5. The average sits a little below because one move in ten is still random, and a random move can waste a step or bump a wall.
The picture at the bottom is the learned policy. For each square we print an arrow for its best-scoring move: ^ up, v down, < left, > right. G is the goal and X is the pit. Follow the arrows from the top-left and you reach the goal. No arrow points into the pit.
Where tables break
Our table had 16 squares times 4 moves, 64 numbers. Easy. But a table needs one row for every state the agent could ever be in. Wikipedia warns: 'Q-learning at its simplest stores data in tables. This approach falters with increasing numbers of states/actions.'
Let us count how fast it grows. We keep the four moves and make the grid bigger.
actions = 4
for side in (4, 100, 1000):
cells = side * side * actions
print(f"{side} x {side} grid: {cells:,} numbers in the Q-table")
print()
# add what the agent carries: 2 keys, each held or not
cells = 4 * 4 * 4 * 2 ** 2
print(f"4 x 4 grid with 2 keys to carry: {cells:,} numbers")Output
4 x 4 grid: 64 numbers in the Q-table 100 x 100 grid: 40,000 numbers in the Q-table 1000 x 1000 grid: 4,000,000 numbers in the Q-table 4 x 4 grid with 2 keys to carry: 256 numbers
A 1,000 by 1,000 grid already needs four million numbers, and tasks with many facts to track grow faster still. The size also jumps if the agent carries extra facts: two keys, each held or not, multiply our 4 by 4 table by four, from 64 to 256.
There is a second limit. Wikipedia says the standard version 'applies only to discrete action and state spaces', meaning a countable list of squares and moves, not smooth values like a steering angle.
Too many rows
The table no longer fits in memory, and most rows are never visited, so they never learn.
No sharing
A table learns each state on its own. Two almost-identical states teach each other nothing.
Only countable choices
Squares and buttons suit a table. A smooth value like a steering angle does not.
The fix is to replace the table with a function that guesses the score, such as a neural network. Wikipedia describes combining Q-learning with function approximation as a way to 'apply the algorithm to larger problems', and says a neural network can be used for it. A network that does this is called a deep Q-network. Wikipedia says DeepMind used a deep convolutional neural network for its system. That is the next lesson.
What to remember
The table
A Q-table holds one score for every move in every state. Using it means picking the biggest score in your row.
The update
After each step, move the old score a fraction (the learning rate) towards: reward plus discount times the best next score.
The limit
It works for small worlds. When the number of states explodes, a table can no longer hold them.
Quick check
You make the grid 10 times wider and 10 times taller, with the same 4 moves. About how big is the new Q-table?
Next: deep Q-networks, when the Q-table is too big to write down.
Sources
Last updated on 16 November 2026
Learn with me
Every lesson is free. I add new ones as I learn. Have a question, or want help with your own work? Book a short call.