---
title: "Q-Learning"
description: "Watch delayed rewards change earlier choices through Q-table updates."
source: https://vizlearn.app/ai/reinforcement/q-learning
---

# Q-Learning

Q-learning is a reinforcement-learning algorithm that learns the value of taking
an action in a state from experience. Each transition updates one Q-table entry
using an observed reward and the largest estimated value at the next state.
Repeated visits let delayed rewards influence earlier choices without requiring
the agent to know the environment's transition model.

Think of a signpost at each junction. Its arrows carry estimates of what you
could earn by taking each direction. Reaching a rewarding exit changes the
estimate on the arrow that led into it. On a later visit, the junction before
that one can learn from the improved signpost. The reward does not rewrite the
whole route at once.

The choice here is between +1 on the next move and +5 three moves away. You can
see both exits on the map; the updater learns only from the moves the agent
tries. Tabular Q-learning fits small, discrete state and action spaces where
you can collect repeated experience without knowing the transition model.

## How Q-Learning Works: One Experience Changes One Estimate

A **state** describes where the agent is. An **action** selects a legal move.
The environment returns an immediate **reward** and a next state. Q(s,a)
estimates the discounted return from taking action a in state s and then
following an optimal policy. Early in training, that estimate can be wrong.
A larger Q value means a more promising action; Q is not an action probability.
An **episode** is one attempt from the start until an exit. Starting a new
episode resets the position and keeps the learned table.

### The target combines a reward with an estimate

The **target** is the reward from this move plus the discounted best estimate
at the next state. You already observed the reward; the future part is still
an estimate. The learning rate alpha controls how far the old Q value moves
toward this target. Here alpha = 0.5, so the old estimate and target meet halfway.

For one observed transition `(s, a, r, s')`, Q-learning forms a target:

```text
future = max over legal a' of Q(s', a')
target = r + gamma * future
Q(s, a) <- Q(s, a) + alpha * (target - Q(s, a))
```

At a terminal state, future is zero: the episode has ended and there is no next
action. The exit reward is already included in r. Every other table entry stays
unchanged. The quantity `target - Q(s,a)` is the temporal-difference error: how
far this new target lies from the old estimate. With alpha = 0.5, the update
moves halfway toward it; a lower target can also pull Q downward.

### Discounting changes which reward is worth pursuing

The discount factor gamma applies once per transition. A reward of 5 received
on the third move contributes `gamma² × 5` to the return from the start. At
gamma = 0.9 that is 4.05; a reward of 1 on the first move contributes 1. At
gamma = 0, only the immediate reward counts. Changing gamma changes the
objective, not just the speed of learning.

### Exploration collects experience; the target uses the maximum

The agent must also decide which experiences to collect. An **epsilon-greedy**
behavior policy draws a uniformly random legal action with probability epsilon;
otherwise it chooses an action with the largest current Q value. A random draw
can select that same maximizing action. "Explore" describes how the action was
sampled, not a promise that the action is worse.

Q-learning is **off-policy**: its target uses the maximum next-state estimate,
even when the behavior policy subsequently samples a different action. SARSA's
on-policy target instead uses the next action actually sampled. Both are
meaningful learning rules; they answer different policy questions.

## Q-Learning Step by Step

The default world has two rows and three columns:

| Small exit: +1 | Wall | Goal: +5 |
| --- | --- | --- |
| S: start | A | B |

You can move between adjacent open cells. At S, legal actions are Up and Right;
at A, Right and Left; at B, Up and Left. Entering either exit gives its reward
and ends the episode. All other moves give zero. The wall and map boundary
make an action unavailable, represented by a dash rather than a zero estimate.

The run starts with all legal Q values at zero, alpha = 0.5, epsilon = 0.35,
gamma = 0.9, and eight episodes. Each episode starts at S and preserves the
table. A fixed random seed of 947 makes the demonstration repeatable. Greedy
ties follow the legal-action orders above, so the first greedy choice at S is
Up. A safety cutoff limits an episode to eight transitions; the longest default
episode uses five, so the cutoff does not affect this trace.

**Episode 1: learn the nearby exit.** The agent takes Up from S and receives 1.
The next state is terminal, so the target is `1 + 0.9 × 0 = 1`.
Q(S,Up) becomes `0 + 0.5 × (1 - 0) = 0.5`. Q(S,Right) stays zero.

**Episode 2: discover the goal.** An exploration draw takes Right to A. Reward
and A's estimates are zero, so Q(S,Right) remains zero. Right from A reaches B;
its target is also zero. Finally, Up from B reaches the goal. Reward 5 and
terminal future zero give target 5, so Q(B,Up) becomes 2.5. The earlier two
entries remain zero: those updates already happened before the reward arrived.

**Episode 3: move the value one junction backward.** Another exploration draw
takes S to A. The start's target is still zero. The subsequent A-to-B move now
reads Q(B,Up) = 2.5. Its target is `0 + 0.9 × 2.5 = 2.25`, and Q(A,Right)
becomes 1.125. Reaching the goal again raises Q(B,Up) from 2.5 to 3.75.

**Episode 4: change the start's preferred action.** Exploration again takes
Right from S. A's best estimate is now 1.125, giving target 1.0125.
Q(S,Right) becomes 0.50625, just above Q(S,Up) = 0.5. The start's greedy
arrow turns Right. The agent finishes the route through B to the goal.

These end-of-episode estimates show why reaching the goal once is not enough:

| After episode | Q(S,Right) | Q(A,Right) | Q(B,Up) |
| --- | --- | --- | --- |
| 2: first goal | 0 | 0 | 2.5 |
| 3: A learns from B | 0 | 1.125 | 3.75 |
| 4: S learns from A | 0.50625 | 2.25 | 4.375 |

Each signpost improves when its own action is tried again. In episode 2, S and
A had already been updated using zeros before B encountered +5. They cannot
use B's new estimate until a later visit.

**Episode 5: separate the target from behavior.** The agent follows
`S → A → B → A → B → goal`. On the first A-to-B transition, Q(B,Up) = 4.375
and Q(B,Left) = 0. Q-learning uses target 3.9375 and updates Q(A,Right)
from 2.25 to 3.09375. The next exploration draw then chooses Left at B.
The target used the best estimated continuation even though behavior took a
detour. Substituting that sampled Left action would have produced target zero
and an updated Q(A,Right) of 1.125 on this same prefix.

Episodes 6 through 8 repeat the direct route and strengthen its estimates. At
the end, Q(S,Right) is approximately 3.27480 and Q(S,Up) remains 0.5.
Training has improved the choice without making every estimate exact.

The final rollout freezes the table and removes exploration. It follows
`S → A → B → goal`, collecting discounted return 4.05. That observed return
and the learned estimate 3.27480 are different quantities. This finite run
demonstrates value propagation; it does not prove convergence.

## When the Q Table Is a Useful Choice

Use a table when states and legal actions can be enumerated and revisited.
The update needs a sampled `(state, action, reward, next state)` transition,
not a labeled correct action. If the transition model and rewards are already
known, planning can use them directly. Compare that planning cost with the cost
of collecting more experience to improve the Q estimates.

Separate the two control decisions. Epsilon changes which experience you
collect. Gamma changes how much delayed rewards count toward your objective.
Lowering gamma to force a quicker-looking result solves a different reward
problem. Evaluate the frozen greedy policy separately from exploratory training
so that a random detour does not masquerade as its preferred action.

## Time and Space Complexity

For S states and at most A legal actions per state, tabular Q-learning uses
O(SA) memory. A greedy choice or next-state maximum takes O(A) time with a
linear scan; committing one table entry takes O(1). Over T sampled transitions,
the time complexity is O(TA). This map has three nonterminal states and two
legal actions at each, so each transition costs constant work.

The number of experiences needed for a useful policy is a separate question
from the cost of one update. Discovering rewards can take far longer than
updating a table. Storing every animation snapshot also costs extra memory; that
is a playback requirement, not part of the learning algorithm.
With many or continuous states, a separate value for every state-action pair
becomes impractical and many entries receive little experience. Function
approximation shares information across inputs, but adds training challenges
that this small table does not model.

## Edge Cases

- **No exploration.** Set epsilon to 0 while keeping gamma at 0.9. Under this
  world's zero initialization and tie rule, all eight episodes take the nearby
  exit. Q(S,Up) reaches approximately 0.99609; Q(S,Right) stays zero. No update
  can extract evidence from an action the agent never tries.
- **Immediate reward only.** Set gamma to 0 with epsilon 0.35. The agent still
  encounters the goal, but Q(A,Right) and Q(S,Right) remain zero. The final start
  estimates are 0.9375 for Up and 0 for Right. Preferring Up is appropriate for
  the immediate-reward objective.
- **Always exploring.** Epsilon 1 samples every behavior action randomly; it
  still uses a maximizing target. The final evaluation remains greedy. Eight
  episodes do not guarantee that all useful experiences have been collected.
- **Terminal versus cutoff.** An exit makes future value zero. Reaching this
  player's eight-transition cutoff does not make the environment state
  terminal: the last transition still uses a nonterminal bootstrap. A repeated
  state during the frozen deterministic rollout is reported as a policy cycle.
- **Ties.** Equal estimates use a fixed action order here. Random tie-breaking
  would produce different experiences; the deterministic rule is disclosed so
  the default experiment can be reproduced.

## Common Mistakes

- Treating Q as the last immediate reward. Its target includes the discounted
  estimate of what can happen after the move.
- Updating every earlier state when a reward arrives. One-step Q-learning
  changes only the experienced state-action pair; earlier entries need later
  visits to use the improved next-state values.
- Putting the exit reward into the target twice. It appears once as r; the
  terminal bootstrap is zero.
- Maximizing over unavailable moves. A dash has no action value and cannot
  win an argmax, even when every legal action has a negative estimate.
- Calling the exploratory trajectory the learned greedy policy. Evaluation
  uses the frozen table and makes its own sequence of choices.
- Assuming eight successful episodes prove optimality. The classical tabular
  theorem requires sufficient repeated sampling and suitable learning-rate
  conditions; fixed alpha over this short run establishes neither. See
  [Watkins and Dayan's original Q-learning paper](https://www.gatsby.ucl.ac.uk/~dayan/papers/cjch.pdf).

## A Note on Simplification

This explainer uses a deterministic grid, state-dependent legal actions, a
tabular estimate, fixed alpha, a curated random seed, and a short episode budget.
It is not a substitute for formal reinforcement-learning study. Stochastic
transitions and large state spaces complicate the problem; deep Q-learning adds
function approximation and commonly uses replay buffers and target networks.
Those mechanisms are omitted here. The viewer sees the map, but the learning
rule uses sampled transitions rather than planning with a known world model.