Q-learning powered nearly every game-playing AI before 2017 — and it still runs underneath modern DQN, Rainbow, and offline RL. Five lines of update rule. Yet understanding it is the difference between memorizing Q(s,a) ← Q(s,a) + α[r + γ max Q − Q] and actually grokking why bootstrapped value propagation converges. Once it clicks, the rest of RL is variations on this theme.
Learning Objectives
After this lesson, you will be able to:
Understand the Bellman equation: how it breaks a big, long-term problem into simple one-step decisions using the recursive Q(s,a) ← Q(s,a) + α[r + γ max Q(s',a') - Q(s,a)] update
Code Q-learning from scratch and watch it learn the best path through a grid maze
Distinguish Q-learning (off-policy: always updates toward the max Q of the next state) from SARSA (on-policy: updates toward the Q of the action actually taken)
Know when Q-learning converges and why the tabular approach fails catastrophically at large state spaces -- and what Deep Q-Networks do instead
This mental map assigns a score to every combination of (location, direction). It tells you, "If you are HERE and go THAT WAY, here is how much total enjoyment you can expect."
That is a Q-table. Q(state, action) is your map of the world's value. Once the map is complete, navigating is trivial: at every intersection, just pick the direction with the highest score.
Q-learning is the algorithm that builds this map through experience -- without ever being told the layout of the city.
Q-learning, introduced by Chris Watkins in 1989, is one of the most important algorithms in reinforcement learning. It learns the optimal action-value function Q* directly from experience, without needing a model of the environment. It is off-policy (it learns about the optimal policy regardless of what exploration strategy it uses) and model-free (it does not learn transition probabilities).
The Bellman equation is the recursive relationship at the heart of Q-learning. It says: the value of being in a state and taking an action equals the immediate reward plus the discounted value of the best action in the next state.
The recursion telescopes: at every step, the optimal Q-value accounts for all future optimal decisions. This is the magic of the Bellman equation -- it lets us solve a multi-step problem by solving many one-step problems.
Q-learning uses the Bellman equation as an update rule. After each experience (state, action, reward, next_state), it nudges the Q-table closer to satisfying the Bellman equation:
alpha is the learning rate (how much to update per experience)
R_ + gamma * max Q(S_, a) is the TD target (what the Bellman equation says Q should be)
Q(S_t, A_t) is the current estimate
The difference is the temporal difference (TD) error -- the surprise
What Do You Think?
After one Q-learning update, will Q(s, a) exactly equal the Bellman target?
Try it! Imagine you are at a crossroads in a maze. Going right gave you +5 last time. Your Q-table says Q(here, right) = 3. The new target is 5. With alpha = 0.1, the update is: 3 + 0.1 * (5 - 3) = 3.2. The Q-value moved a little toward the truth. Run this in your head a few more times and you will see it converge toward 5.
The learning rate alpha (typically 0.01 to 0.1) controls what fraction of the TD error to apply. With alpha = 1.0, Q would jump to the target immediately, but this causes instability because the target itself changes as Q changes. Small alpha values ensure smooth, stable convergence.
Create a table with one row per state and one column per action. Initialize all Q-values to zero (or small random values). Our gridworld has 16 states (4x4 grid) and 4 actions (up, down, left, right). The Q-table has 16 x 4 = 64 entries, all starting at zero.
The agent starts at the top-left corner. It knows nothing -- every state-action pair looks equally worthless. The Q-table is a blank map waiting to be filled with experience.
The agent must choose an action. With probability epsilon (e.g., 0.1), it picks a random action to explore the unknown. With probability 1 - epsilon, it picks the action with the highest Q-value to exploit what it has learned.
Early in training, all Q-values are zero, so even the "greedy" choice is effectively random. As Q-values develop, the greedy choice becomes increasingly informed. Epsilon-greedy ensures the agent never stops exploring entirely.
The agent executes its chosen action. It moves right. The environment responds with a new state (the next cell) and a reward (-0.04 step penalty). The agent now has its first experience tuple: (s=0, a=right, r=-0.04, s'=1).
This single experience contains everything needed for a Q-learning update: where it was, what it did, what it got, and where it ended up.
Apply the Bellman update. Target = r + gamma * max Q(s', a') = -0.04 + 0.99 * 0 = -0.04. The TD error is target - current = -0.04 - 0 = -0.04. Update: Q[0][right] = 0 + 0.1 * (-0.04) = -0.004.
The Q-table now has one non-zero entry. The agent has learned that going right from the start has a small cost. The key insight: the max over next-state Q-values means the agent always updates toward the optimal future, regardless of what exploratory action it actually takes next.
The agent transitions to state s' and the loop repeats. From this new state, it again chooses an action via epsilon-greedy, takes the action, observes the result, and updates Q. Each update propagates value information one step backward through the state space.
After reaching the goal (reward +1), that reward signal slowly backs up through the Q-table -- first to states adjacent to the goal, then to states two steps away, then three, and so on. After 100 episodes, states near the goal have high Q-values. After 1000 episodes, the value gradient reaches the start.
After enough episodes, every Q-value converges to satisfy the Bellman equation. The Q-table is now a complete "value map" of the environment. The optimal policy is trivially extracted: at each state, pick the action with the highest Q-value.
The agent has discovered the shortest path from start to goal, entirely through trial and error. No teacher told it the layout of the grid. No planner computed the path. Q-learning built the map one experience at a time.
Loading visualization...
Try it: Watch Q-Values LearnInteractive
Observe Q-learning in action on a grid world. Each cell displays Q(s,a) for all four actions as colored triangles. Brighter colors mean higher values. As the agent explores, Q-values propagate backward from the goal, eventually revealing the optimal path through policy arrows.
Q-learning is guaranteed to converge to the optimal Q-function Q* under certain conditions:
Every state-action pair is visited infinitely often. The agent must keep exploring (epsilon-greedy with a decaying but non-zero epsilon ensures this).
The learning rate decays appropriately. It must satisfy the Robbins-Monro conditions: the sum of learning rates diverges (sum alpha_t = infinity) but the sum of squared learning rates converges (sum alpha_t^2 < infinity). In practice, a fixed small learning rate works well enough.
The MDP has finite states and actions. The tabular approach requires enumeration.
Q_t(s, a) \xrightarrow{t \to \infty} Q^*(s, a) \quad \text{if } \sum_{t} \alpha_t = \infty \text{ and } \sum_{t} \alpha_t^2 < \infty
Q-learning updates toward the max Q-value of the next state (what the optimal policy would do). SARSA updates toward the Q-value of the action actually taken in the next state (what the current policy did):
When does this matter? In "cliff walking" problems, Q-learning finds the shortest path along the cliff edge (optimal but risky). SARSA finds a safer path farther from the cliff because it accounts for the chance that epsilon-greedy exploration will cause a fall.
Backgammon (~10^20 states): impossible to store a table
Atari games (210 x 160 x 3 pixels = 10^67,000 possible states): laughably impossible
What Do You Think?
An Atari game screen has 210 x 160 pixels, each with 256 possible color values. How many possible states exist?
The answer is 256^(210*160), an astronomically large number -- far more than atoms in the observable universe. You cannot build a table that large. This is why tabular Q-learning cannot solve real-world problems with high-dimensional observations. The solution? Replace the table with a neural network that can generalize across similar states. That is Deep Q-Networks -- the subject of the next lesson.
Tests · After training, verify Q[0][1] > Q[0][0] (right is better than left at start). Verify Q[3][1] > Q[3][0] (right is better at state 3, which is adjacent to the goal).
The Bellman equation decomposes long-horizon problems. The value of a state-action pair equals the immediate reward plus the discounted value of the best next state, turning a complex sequential problem into iterative one-step updates
Q-learning updates values by bootstrapping. Instead of waiting for complete episodes, Q-learning updates Q(s,a) after each step using the estimated value of the next state, enabling online learning
Tabular Q-learning converges under specific conditions. Every state-action pair must be visited infinitely often and the learning rate must decay appropriately; in practice, this limits Q-tables to small, discrete state spaces
The discount factor gamma controls time horizon. High gamma (near 1) values long-term rewards, low gamma values immediate rewards; this single parameter fundamentally changes the learned behavior
Interactive Lab
Step through Q-learning on a small grid one transition at a time — watch the Bellman update propagate value from the goal back toward the start, cell by cell, until the optimal policy emerges from the table.
Slide γ from 0 to 1 and watch the agent's behavior shift from greedy short-sightedness to long-horizon planning — the single hyperparameter that defines what the agent considers 'the future'.
What does the Bellman equation decompose the optimal Q-value into?
You now understand Q-learning -- the foundational algorithm for learning value functions from experience. But tabular Q-learning hits a wall with large state spaces. Next up: Deep Q-Networks, where a neural network replaces the Q-table and scales RL to complex environments like Atari games.