Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 37 ยท Q-learning and SARSA

The Q-learning Algorithm

Learn tabular Q-learning: the Q-table, the update rule, off-policy learning and epsilon-greedy exploration, with a complete gridworld agent you can run and edit.

In the previous chapters you met value functions and the Bellman equations, and you saw how dynamic programming solves a problem when the model of the environment is known. Real agents rarely get a model. They get experience: a state, an action, a reward and a next state. Q-learning turns that stream of experience into an optimal policy without ever learning the transition probabilities.

Q-learning is the most famous tabular reinforcement learning algorithm, and nearly every deep RL method (including DQN, which you will meet in Neural networks as Q-functions) is a descendant of it. In this lesson you will build it from scratch with nothing but NumPy.

The action-value table

An action-value function Q(s, a) estimates the expected discounted return if you take action a in state s and then act well. In the tabular setting we store one number for every state-action pair: a table with one row per state and one column per action.

flowchart LR
    A["Agent<br/>holds Q table"] -->|"action a"| E["Environment"]
    E -->|"reward r, next state s'"| A
    A -->|"update Q(s,a)"| A

Each step of experience nudges one cell of the table.

If the table were perfect (Q*), acting optimally would be trivial: in every state pick the action with the largest value. Learning is the process of making the table less wrong.

The update rule

After taking action a in state s, receiving reward r and landing in state s', Q-learning updates one cell:

TEXT
Q(s, a)  <-  Q(s, a) + alpha * ( r + gamma * max_a' Q(s', a')  -  Q(s, a) )

Read it in three parts:

  • r + gamma * max Q(s', a') is the target: what we just saw (the reward) plus our own best estimate of the future.
  • target - Q(s, a) is the TD error: how wrong the old estimate was.
  • alpha is the learning rate: the fraction of the error we correct per step.

This is a sample version of the Bellman optimality equation. Because it bootstraps from Q(s', .), it can learn after every single step, not only at the end of an episode.

If s' is terminal, there is no future: the target is just r. Forgetting this is the most common bug in hand-written Q-learning.

Off-policy: learn the best while behaving badly

The max in the target means Q-learning evaluates the greedy policy, no matter which action the agent actually takes next. The agent can explore randomly and still learn the value of acting optimally. This is called off-policy learning: the behavior policy (what generates data) differs from the target policy (what is being learned).

For behavior we normally use epsilon-greedy: with probability epsilon pick a random action, otherwise pick argmax Q(s, .). Without exploration, an agent might never discover a better route. Exploration strategies goes deeper.

A complete gridworld agent

Our world is a small grid. S is the start, G the goal (reward +10), P a pit (reward -10), # a wall. Every other step costs -1, so shorter paths are better.

Python Q-learning on a gridworld

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Run it and read the arrows: starting at the top-left the agent should walk around the pits to the goal in the fewest steps. Try epsilon = 0 and watch what happens: with an all-zero table, argmax always picks action 0 (up), so the agent keeps bumping into the wall and rarely discovers anything.

Watching the learning curve

A single policy printout hides the learning process. Track the return per episode and average it in blocks:

Python Learning curve and the effect of alpha

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A tiny alpha learns slowly; a large one learns fast here because the world is deterministic. With noisy rewards, a large constant alpha keeps the table jittering, which is why many implementations decay it.

When does Q-learning converge?

In the tabular case Q-learning converges to Q* with probability 1 if every state-action pair is visited infinitely often and the learning rates shrink appropriately (they sum to infinity while their squares sum to a finite number). In practice we use a small constant alpha and a decaying epsilon and accept "close enough". Convergence guarantees break down once you replace the table by a neural network; see the deadly triad.

Common mistakes

  • Bootstrapping from the next state of a terminal transition.
  • Using epsilon = 0 from the first step, so the agent never explores.
  • Mixing up the tables for different states (copying a Q row instead of indexing it).
  • Never capping episode length, which can loop forever when the policy is bad.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the max in the Q-learning target do?

    The max evaluates the greedy policy in the next state, whatever the agent really does there. That is what makes Q-learning off-policy.
  2. 2. What is the target for a transition that ends the episode?

    A terminal state has no future return, so the target is just the reward.
  3. 3. Why does Q-learning still need an exploration strategy such as epsilon-greedy?

    Cells that are never tried are never improved. Exploration keeps collecting data about alternatives.
  4. 4. What is the TD error?

    TD error = (r + gamma * max Q(s', .)) - Q(s, a). The update moves Q(s, a) a fraction alpha of the way toward the target.

Summary

  • Q-learning stores Q(s, a) and updates it with Q += alpha * (r + gamma * max Q(s', .) - Q).
  • It is off-policy: it learns the greedy policy while following an exploratory one.
  • Terminal transitions use only the reward as target.
  • Epsilon-greedy exploration and a sensible alpha decide how fast and how reliably it learns.

Next: SARSA: On-policy TD Control