Q-Learning
Value iteration needs the full model . But agents in the real world don't get a rulebook — they learn by doing. Q-Learning is the landmark model-free algorithm: it learns the optimal action-value function from raw experience, with no model of the environment, and provably converges to the optimum.
Real-world examples: Game agents, robot navigation, traffic-light control, simple trading bots, the conceptual core of the DQN that cracked Atari.
Temporal Difference learning
The trick is to turn the Bellman equation into a learning rule. After taking action in state and observing reward and next state , we have a sample of the Bellman backup. We nudge our current estimate toward this sample:
The bracket is the TD error — the gap between what we predicted and the bootstrapped target. is the learning rate.
Intuition
You guessed a state was worth 10. You act, collect a reward, and land somewhere your own table says is worth 15 (discounted). Your guess was too low — bump it up. Temporal difference learning means correcting each prediction using the very next prediction, without waiting for the final outcome. You learn during the episode, not just at the end.
Watch the Q-table fill in over 200 episodes — Q-values propagate from the goal outward and the greedy policy converges to the optimal path:
Q-Table — ε-greedy Q-Learning
Each episode runs ε-greedy Q-learning from S to G. Watch Q-values propagate from the goal outward, and the policy arrows converge to the optimal path. Adjust ε and α to see their effect on convergence speed.
Why "off-policy"?
Notice the update uses (the value of the best next action) regardless of which action the agent actually takes next. This makes Q-learning off-policy: it learns the optimal policy while behaving with a different, exploratory policy.
| On-policy (SARSA) | Off-policy (Q-learning) | |
|---|---|---|
| Target uses | : action actually taken | : best action |
| Learns | Value of the behavior policy | Value of the optimal policy |
| Behavior | More conservative near risk | Learns optimum even while exploring |
The exploration–exploitation dilemma
To learn good values the agent must explore (try unknown actions) yet to score well it must exploit (take known-good actions). The standard balance is -greedy: with probability act randomly, otherwise act greedily.
Typically starts high (~1.0, explore a lot) and decays toward a small floor (~0.01) as the agent gains confidence.
Explore early, exploit late
At the start the Q-table is garbage, so exploiting it is pointless — explore widely. As estimates sharpen, shift toward exploitation. Decaying over training implements exactly this schedule.
The algorithm
- Initialize arbitrarily (e.g. zeros).
- For each episode, from the start state, repeat until terminal:
- Choose from using -greedy.
- Take ; observe , .
- Update .
- .
- Decay .
Worked example: one update
, . Current . Agent takes , gets , lands in where .
TD target . TD error . New .
Watch it learn
That update, then the same rule run to convergence on a cliff world the agent knows nothing about:
Q-learning — bootstrapping from experience, and the word that makes it SARSA
A 3×6 cliff world. Start bottom-left, goal bottom-right, and the whole bottom row between them is a cliff: step in and you take −100 and get teleported back to the start. Every other step costs −1. Unlike value iteration, the agent is given **no model** — it does not know where the cliff is, and has to find out by falling in.
| c0 | c1 | c2 | c3 | c4 | c5 | |
|---|---|---|---|---|---|---|
| r0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 |
| r1 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 |
| r2 | 0.0 | · | · | · | · | 0.0 |
Cells shown as · are the cliff. The agent has no idea they are special until it lands on one.
Q-learning on a cliff world the agent knows nothing about, starting from the lesson's single worked update and running out to convergence. Watch value propagate backwards from the goal exactly as it does in value iteration — except every increment here came from a sampled transition rather than a model. The final step changes one expression in the target, turning the same code into SARSA, and the two learn genuinely different routes: Q-learning hugs the cliff edge because the max ignores its own exploration, SARSA detours because its target does not.
What to notice as you step:
- The agent learns the cliff exists by falling into it. There is no model to consult — the first −100 is the entire source of that knowledge, and means one fall only moves the estimate halfway.
- Value propagates backwards from the goal, exactly as in value iteration, but every increment came from a sampled transition instead of a known .
- The last step changes one expression:
max Q(s', b)becomesQ(s', a'), the action actually about to be taken, and the same code is SARSA. On identical experience the two learn different routes: Q-learning hugs the cliff edge (optimal, because the max ignores its own exploration), SARSA detours along the top (because its target feels every exploratory fall). - The safer policy earns more while learning: SARSA averages −18.5 per episode against Q-learning's −22.5. Q-learning would win if you switched exploration off at deployment. Which you want depends on whether falling off the cliff during training is survivable.
import numpy as np
import gymnasium as gym
env = gym.make("FrozenLake-v1", is_slippery=False)
Q = np.zeros((env.observation_space.n, env.action_space.n))
alpha, gamma, episodes = 0.8, 0.95, 2000
epsilon, eps_min, eps_decay = 1.0, 0.01, 0.999
for ep in range(episodes):
s, _ = env.reset()
done = False
while not done:
# ε-greedy action selection
if np.random.rand() < epsilon:
a = env.action_space.sample()
else:
a = int(np.argmax(Q[s]))
s2, r, term, trunc, _ = env.step(a)
done = term or trunc
# Q-learning update (off-policy: uses max over next actions)
Q[s, a] += alpha * (r + gamma * np.max(Q[s2]) - Q[s, a])
s = s2
epsilon = max(eps_min, epsilon * eps_decay)
print("Learned Q-table:\n", np.round(Q, 2))
print("Greedy policy:", np.argmax(Q, axis=1))
Convergence guarantee
Q-learning provably converges to for any finite MDP, provided every state–action pair is visited infinitely often and the learning rate satisfies the Robbins–Monro conditions (, ). In practice a small constant or slowly decayed works fine.
The wall: big state spaces
The Q-table has one entry per . That's fine for a 16-cell grid, hopeless for chess ( states) or Atari (every screen of pixels). A table can't generalize to states it hasn't seen. The fix (replace the table with a neural network that approximates ) is the Deep Q-Network, the next lesson.
Tabular Q-learning doesn't scale
Tabular Q-learning needs to visit (nearly) every state. Beyond a few thousand states it becomes infeasible — both to store and to explore. Function approximation is mandatory for real problems.
Exercise
With α=0.1, γ=0.9, current Q(s,a)=5, reward r=2, and max Q(s',·)=10, what is the updated Q(s,a)?
Need a hint?
TD target = r + γ·max Q(s'); new Q = old + α·(target − old).
Exercise
Why is Q-learning called 'off-policy'?
Need a hint?
Look at which next action the update's target uses.
Exercise
In ε-greedy exploration, why is ε typically decayed over training?
Need a hint?
How good is the Q-table at the start vs later?
Exercise
Set the initial ε for ε-greedy exploration at the start of Q-learning (before any decay).
Need a hint?
At the very start, the Q-table contains random values. Pure exploitation of noise leads nowhere.
Common mistakes
- No exploration: pure greedy from a zero-initialized table gets stuck; always use -greedy (or optimistic init).
- Learning rate too high: near 1 makes thrash on noisy rewards; use a moderate or decaying .
- Confusing SARSA with Q-learning: SARSA uses the taken next action (on-policy); Q-learning uses the max (off-policy). They learn different things in risky environments.
Key takeaways
- Q-learning turns the Bellman equation into a TD update from sampled experience.
- It is off-policy — the target uses the best next action regardless of behavior.
- ε-greedy balances exploration vs exploitation; decay ε over training.
- Tabular Q-learning can't scale to large state spaces.
Related concepts
- Markov Decision Processes: the Bellman foundation it samples
- Deep Q-Networks: scaling Q-learning with a neural network