Your First Q-Table

#A Small World to Walk In

Picture a board with nine squares in three rows of three. You put a token on the top left square. Somewhere on the board there is a prize, and somewhere there is a pit. You may move the token one square at a time: up, right, down or left. If you bump into the edge, the token stays where it is. Your aim is to reach the prize.

We number the squares 0 to 8, left to right, top to bottom, so we can talk about them without confusion.

In one sentence: the world is nine squares, four moves, and scores of -1 per step, +10 for the prize and -10 for the pit.

#The Q-Table: A Notebook of Move Scores

The agent has no map. It starts knowing nothing, so it needs a place to write down what it learns. The simplest place is a table with one row for each square and one column for each move. Each cell of the table holds one number: how good the agent believes that move is when standing on that square.

At the start the agent knows nothing, so every cell is 0. Here are a few of the 36 cells, as a small excerpt.

In one sentence: the Q-table has one number for every (square, move) pair, it starts at zero, and the biggest number in a square's row is the best move so far.

#The Update: One Small Sum

How does a number in the table get better? Every time the agent makes a move, it learns two facts: the reward it just got, and where it landed. It also has its old guess for that move. The update mixes them.

The update as a line:

new Q = old Q + alpha x (target - old Q)
target = reward + gamma x (best Q in the square I landed on)

Read the part in brackets as "how wrong was I?". The target minus the old Q is the gap. Moving alpha times the gap closes part of it. If alpha were 1, we would jump straight to the target. If alpha were 0, we would never learn.

Special case: if the move ended the walk, there is no future, so the best Q of the next square counts as 0.

In one sentence: each move nudges its Q-value part of the way from the old guess toward the reward plus a share of the best value ahead.

#Be the Agent: Four Steps by Hand

Now do it on paper. Start with the all-zero table and walk a route we choose by hand: from square 0 right, from 1 right, from 2 down, from 5 down. This walks along the top row and then down the right column to the prize. We use alpha 0.5 and gamma 0.9.

Look at what the table now holds: three entries of -0.5 and one entry of 5. The prize has been noticed, but only in the very last entry. Squares 0, 1 and 2 have only heard that each step costs a point.

Now walk the same route a second time. The first two updates give -0.75 each, because the best value known in the next square is still 0 from an untried move, so the target is -1 and half of the gap from -0.5 is -0.25 more. The interesting part comes at square 2.

Notice that square 2's number just turned positive. It changed because square 5 now has a good value, and square 2 looked ahead at it. The news of the prize moved one square back along the route. This is the central idea: good news spreads backward, one step per walk, because each cell learns from the best cell just ahead of it.

Check your hand work with the program below. It runs the same two walks with the same numbers and prints each updated cell. Compare every line with the sums above before you trust it.

Do: Press Run and match each printed line to a step above. Then change ALPHA = 0.5 to ALPHA = 1.0 and run again.

Notice: The first walk prints -0.50, -0.50, -0.50 and 5.00. The second walk prints -0.75, -0.75, 1.50 and 7.50, so the third line has turned positive. With ALPHA at 1.0 each walk jumps straight to its target: after walk 1 the last entry is 10.00, not 5.00.

Why: Alpha is how much of the gap you close each time. At 0.5 you close half and creep toward the target. At 1.0 you jump to it, which is fast but trusts every single sample completely, and that can swing wildly when the rewards are noisy.

In one sentence: with a few small sums, each cell gets nudged toward the reward plus the best value ahead, and the prize news moves back one square per walk.

#The Pit: Learning What to Avoid

So far only good news has moved around. Bad news moves the same way, and it matters just as much. Suppose the agent, standing on square 1, steps down into the pit at square 4. The reward is -10 and the walk ends.

Now square 1's row has right at -0.5 and down at -5. A greedy agent standing on square 1 compares the numbers and prefers right (-0.5 is bigger than -5). It will avoid the pit without anyone telling it "the pit is dangerous". It learned this by falling in once.

But there is a catch you can see in the tables above. Moves never tried still hold 0, and 0 is bigger than -0.5. A purely greedy agent would therefore prefer an untried move over a tried move that cost a point. That helps, because it forces the agent to try things, but only by accident. A better plan is the one from the last lesson: choose the greedy move most of the time, and a random move a small share of the time. The same epsilon-greedy rule works here, with 0.2 meaning 1 time in 5 the agent tries a random move.

In one sentence: bad news spreads like good news, a pit teaches the agent a strongly negative number for the move that led to it, and a small amount of random exploring keeps the agent trying moves it has not tried.

#Let the Machine Do 300 Walks

Filling the table by hand for every cell would take hours. A program does it in a blink. The cell below trains on the same grid with epsilon-greedy choice: 20 percent random moves, otherwise the best Q-value so far. After training it prints the best move in each square as an arrow. G marks the prize and P the pit.

We print four snapshots, after 0, 5, 30 and 300 walks. Before you run it, predict: after 0 walks the table is all zeros, so what arrows do you expect?

Do: Press Run. Then change the last number 0.2 in ALPHA, GAMMA, EPSILON = 0.5, 0.9, 0.2 to 0.0 and run again, then to 0.9.

Notice: After 300 walks with EPSILON 0.2 the grid reads v > v, v P v, > > G: every arrow leads toward the prize and none points into the pit. EPSILON 0.0 and 0.9 also reach the prize on this tiny grid, though with 0.0 the start cell holds only -2.11 for right, so the table is thinner.

Why: Every step costs -1, so a move never tried (0) looks better than one that cost a point, and a greedy agent stumbles into new moves. That luck belongs to this small board. With sparse prizes, a greedy agent can freeze on the first route that worked.

Last, watch a bigger version learn. The demo below runs the same Q-update on a 4 by 4 grid with a prize and a cliff. It fills in a Q-table as it goes, and the cells change colour as values grow or shrink.

Do: Press Play and let a few dozen walks go by. Then press Reset, set the Exploration slider near its minimum, and Play again.

Notice: Values near the goal turn green first. Over time the green spreads backward along the route, one square at a time, just as in your hand trace. With exploration near zero, the agent may fix on one route and leave many cells at zero.

Why: Each cell learns from the best cell just ahead of it, so value must travel backward from the goal. Exploration decides how much of the grid the agent ever visits.

In one sentence: a program applies the same small sum thousands of times, and the table ends up holding a route from the start to the prize.

#What the Table Cannot Do

The Q-table is a beautiful first method, and it has one hard limit. It needs one row for every possible state. Our board has 9 squares, so the table has 36 cells. A chess position has more possible states than anyone can write down, and a camera image has even more. A table that big cannot be stored, and the agent would never visit most rows anyway.

So bigger problems replace the table with a formula that guesses the numbers, which can be a neural network. That is the subject of the Deep Q-Networks lesson further on. The update you did by hand today is still the heart of it. Learning the table first is like learning long division before using a calculator: the steps you did by hand are the ones the calculator runs for you.

A second limit is that we, the designers, chose the scores. If the pit paid -1 instead of -10, the agent would treat it as an ordinary step and might route through it. The reward design lesson later in the track looks at that choice closely.

In one sentence: a Q-table works for small worlds and stops working when the number of states gets too big, which is why later lessons replace it with a learned formula.

#Where to Go Next

• Next: RL Foundations gives the formal words for what you did: Markov decision process, policy, value and the Bellman equation.
• Then: Exploration vs Exploitation goes deeper on the tug between trying and repeating.
• Q-learning in full: Q-Learning covers the on-policy cousin called SARSA and bigger grids.
• Earlier: Reinforcement Learning: Start Here if you want to revisit the loop and the slot machines.

This track has five levels. This is Level 0, the start. After it come the foundations, the core algorithms, the advanced methods, and the expert topics.

In one sentence: read RL Foundations next, then follow the track in order.

#Key Takeaways

• A Q-table holds one number for every (square, move) pair, and all of them start at zero
• Each move nudges one number toward a target: the reward just received plus a discounted share of the best value in the square landed on
• Good news moves backward through the table about one square per walk, because each cell learns from the best cell just ahead
• A pit teaches a strongly negative number, so a greedy agent learns to avoid it without being told
• A small share of random moves keeps the agent testing alternatives, and the table works only while the number of states stays small

#Quick Check