AlgoPlusAlgoPlus
Learn/Machine Learning
Lesson

Q-Learning

Learn the value of each action by trial and error — no map of the world required.

9 min read Watch it move Build it

Q-learning learns good behaviour without ever being told how the world works. It keeps a Q(s, a) value for each state-action pair — an estimate of the total future reward that move is worth — and refines those estimates purely from experience. The 'Q' stands for the quality of a move.

The Bellman update

After taking action a in state s, receiving reward r, and landing in s', nudge the old estimate toward a better target: the reward just earned plus the discounted value of the best move available next.

Q(s, a) <- Q(s, a) + α · [ r + γ · max_a' Q(s', a')  -  Q(s, a) ]
                            \________ target ________/   \__ old __/
# α = learning rate   γ = discount   the bracket is the TD error
Bootstrapping: learn a guess from a guess
Notice the update uses Q(s', a') — its *own current estimate* of the next state — as part of the target. This is temporal-difference (TD) learning: each value is refined toward a slightly-better-informed version of itself, and correct values gradually spread backward from the rewarding states.

Explore vs exploit

  1. 1To improve, the agent must try unfamiliar actions (exploration).
  2. 2To do well, it should repeat its best-known move (exploitation).
  3. 3ε-greedy balances them: with small probability ε act at random, otherwise take the highest-Q action.
  4. 4Shrink ε over time — explore early, exploit once confident.
Off-policy
The target uses max_a' Q(s', a') — the value of the *best* next action — even if the agent actually took a random exploratory one. So Q-learning learns the optimal policy while *behaving* with a different, exploratory one. That's what 'off-policy' means.
Tables don't scale
A Q-table needs an entry per state-action pair, which explodes for large or continuous state spaces. The fix is to approximate Q with a neural network — that's Deep Q-Networks (DQN), the method that learned to play Atari from pixels.
OperationTimeSpace
Per step · the max over actions + table storageO(|A|)O(|S| · |A|)
Convergence · to Q* given enough exploration and decaying αmany episodes—
Check yourself
Why is Q-learning called 'off-policy'?