Q-learning: learning from experience

Value iteration, from the last lecture, computes perfect values — but only because it knows the rules of the world: every transition probability and every reward. A real robot, a trading agent or a recommendation system is rarely handed such a model. It has to learn from experience: act, observe what happens, and improve.

Q-learning (Watkins, 1989) is the classic algorithm for doing exactly that. It is simple enough to write in ten lines, and the same idea — scaled up with neural networks — learned to play Atari games from raw pixels.

The idea: learn Q directly

Instead of state values, Q-learning keeps a table of action values $Q(s, a)$: how good it is to take action $a$ in state $s$. Having $Q$ is enough to act: in each state, pick the action with the largest $Q$.

The agent starts with a guess (here, all zeros). After every single step it sees four things — where it was, what it did, the reward it got and where it landed — and updates one entry:

The TD target is a better estimate than the old value, because it includes one real reward. The difference between the target and the old value is the TD error (“temporal difference”). The learning rate $\alpha$ decides how far to move towards the target.

Step through a first episode. Every ordinary move pushes its Q-value down towards −1. Nothing interesting happens until the robot stumbles into a pit or onto the goal — and then the next episodes carry that news backwards, one step at a time, exactly like the sweeps of value iteration.

Model-free

Learning without knowing the transition probabilities or reward function — only from observed experience.

TD target

r + γ · max Q(s′, ·): one real reward plus the current estimate of the future.

TD error

TD target minus the current estimate. Large errors mean the agent was surprised.

Learning rate α

How far each update moves towards the target: large α learns fast but noisily, small α learns slowly but steadily.

Off-policy

Learning about the best (greedy) policy while following a different, exploratory one.

Watch it learn

The robot below starts knowing nothing. Each tile is split into four triangles, one per action, colored by its Q-value: teal for actions that lead somewhere good, coral for actions that lead to trouble. Press Learn.

What to watch for:

• The first episodes are chaotic. The robot wanders, bumps into walls and falls into pits. Each fall paints the triangle pointing into the pit coral.
• Value flows backwards. Triangles pointing towards the goal turn teal first near the goal, then further and further away.
• Exploration never stops. With ε = 0.1 the robot still takes a random move one time in ten, so even a well-trained agent sometimes wanders — its average return stays a little below +3.
• Set ε to 0.5 and training becomes a random walk; set α to 1 and each update jumps all the way to the latest target.

How much to explore

Exploration settings interact with where the values start. In our grid world the true values are mostly negative, so starting every estimate at 0 is optimistic: untried actions look better than tried ones, which drives the agent to try them. That built-in curiosity is a well-known exploration trick.

• With optimistic starting values even ε = 0 learns quickly, and every unit of random exploration only costs return.
• With pessimistic starting values, ε = 0 never finds the goal: once an action has been tried, untried actions look worse forever. Some exploration is essential.
• Decaying ε — exploring a lot at first and less over time — is a robust middle ground and the usual default in practice.

Q-learning in code

import random
from collections import defaultdict

Q = defaultdict(lambda: [0.0, 0.0, 0.0, 0.0])   # Q[state][action]
alpha, gamma, epsilon = 0.5, 0.9, 0.1

for episode in range(500):
    state, done = env.reset(), False
    while not done:
        if random.random() < epsilon:
            action = random.randrange(4)                 # explore
        else:
            action = max(range(4), key=lambda a: Q[state][a])   # exploit
        next_state, reward, done = env.step(action)
        target = reward if done else reward + gamma * max(Q[next_state])
        Q[state][action] += alpha * (target - Q[state][action])  # TD update
        state = next_state

You now have the core of reinforcement learning: the agent–environment loop, the explore–exploit trade-off, Markov decision processes, value functions and learning from experience. The rest of the course scales these ideas up — to function approximation, policy gradients and actor–critic methods such as PPO, and to reinforcement learning from human feedback, the technique that turned large language models into helpful assistants.