Q-LearningOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

Q-Learning

Value iteration needs the full model P,RP, R. 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 Q∗Q^* 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 aa in state ss and observing reward rr and next state s′s', we have a sample of the Bellman backup. We nudge our current estimate Q(s,a)Q(s,a) toward this sample:

Q(s,a)←Q(s,a)+α[r+γmax⁡a′Q(s′,a′)⏟TD target−Q(s,a)⏟old estimate]Q(s,a) \leftarrow Q(s,a) + \alpha\Big[\underbrace{r + \gamma \max_{a'} Q(s', a')}_{\text{TD target}} - \underbrace{Q(s,a)}_{\text{old estimate}}\Big]

The bracket is the TD error — the gap between what we predicted and the bootstrapped target. α\alpha 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

Policy & ValueS#G+1
Q-Table (state × action)↑↓←→0.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.00S0,10,20,31,0#1,21,32,02,12,22,33,03,13,2G
episode0
ε0.10
α0.5
max Q0.000

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 max⁡a′Q(s′,a′)\max_{a'} Q(s', a') (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 π∗\pi^* while behaving with a different, exploratory policy.

On-policy (SARSA)Off-policy (Q-learning)
Target usesQ(s′,a′)Q(s', a'): action actually takenmax⁡a′Q(s′,a′)\max_{a'} Q(s', a'): best action
LearnsValue of the behavior policyValue of the optimal policy
BehaviorMore conservative near riskLearns 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 ε\varepsilon-greedy: with probability ε\varepsilon act randomly, otherwise act greedily.

a={random actionwith prob εarg⁡max⁡aQ(s,a)with prob 1−εa = \begin{cases} \text{random action} & \text{with prob } \varepsilon \\ \arg\max_a Q(s,a) & \text{with prob } 1-\varepsilon \end{cases}

Typically ε\varepsilon 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 ε\varepsilon over training implements exactly this schedule.

The algorithm

  1. Initialize Q(s,a)Q(s,a) arbitrarily (e.g. zeros).
  2. For each episode, from the start state, repeat until terminal:
    • Choose aa from ss using ε\varepsilon-greedy.
    • Take aa; observe rr, s′s'.
    • Update Q(s,a)←Q(s,a)+α[r+γmax⁡a′Q(s′,a′)−Q(s,a)]Q(s,a) \leftarrow Q(s,a) + \alpha[r + \gamma \max_{a'} Q(s',a') - Q(s,a)].
    • s←s′s \leftarrow s'.
  3. Decay ε\varepsilon.

Worked example: one update

α=0.1\alpha = 0.1, γ=0.9\gamma = 0.9. Current Q(s,a)=5Q(s,a) = 5. Agent takes aa, gets r=2r = 2, lands in s′s' where max⁡a′Q(s′,a′)=10\max_{a'} Q(s', a') = 10.

TD target =2+0.9⋅10=11= 2 + 0.9 \cdot 10 = 11. TD error =11−5=6= 11 - 5 = 6. New Q(s,a)=5+0.1⋅6=5.6Q(s,a) = 5 + 0.1 \cdot 6 = 5.6.

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

1/9

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.

python
1def learn(env, episodes, alpha, gamma, eps,
2 on_policy=False):
3 Q = defaultdict(float)
4 for _ in range(episodes):
5 s = env.start
6 a = eps_greedy(Q, s, eps)
7 while not done:
8 s2, r, done = env.step(s, a)
9 a2 = eps_greedy(Q, s2, eps)
10 # the one line that decides everything
11 future = (Q[s2, a2] if on_policy
12 else max(Q[s2, b] for b in A))
13 target = r + gamma * (0 if done
14 else future)
15 td = target - Q[s, a]
16 Q[s, a] += alpha * td
17 s, a = s2, a2
18 return Q
state
V(s) = max_a Q(s,a) — all zero, and the cliff cells are never visited
c0c1c2c3c4c5
r00.00.00.00.00.00.0
r10.00.00.00.00.00.0
r20.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 α\alpha 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 PP.
  • The last step changes one expression: max Q(s', b) becomes Q(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.
Python
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 Q∗Q^* for any finite MDP, provided every state–action pair is visited infinitely often and the learning rate satisfies the Robbins–Monro conditions (∑α=∞\sum \alpha = \infty, ∑α2<∞\sum \alpha^2 < \infty). In practice a small constant or slowly decayed α\alpha works fine.

The wall: big state spaces

The Q-table has one entry per (s,a)(s, a). That's fine for a 16-cell grid, hopeless for chess (104710^{47} 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 QQ) 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).

00.501
Need a hint?

At the very start, the Q-table contains random values. Pure exploitation of noise leads nowhere.

Common mistakes

  1. No exploration: pure greedy from a zero-initialized table gets stuck; always use ε\varepsilon-greedy (or optimistic init).
  2. Learning rate too high: α\alpha near 1 makes QQ thrash on noisy rewards; use a moderate or decaying α\alpha.
  3. 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

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelated
Q-LearningNeural NetworksProbabilistic Models & EMMarkov Decision ProcessesDeep Q-NetworksExploration Strategies & …Diversity, Cold Start & E…