Visual walkthrough — Q-learning algorithm

We assume you have never seen the notation $Q$, $\gamma$, $\max$, or $\leftarrow$. Every one of these is earned before it is used.

---

Step 1 — What are we even trying to measure?

WHAT. Picture a little robot standing on one square of a grid. It can step in four directions. We want a single number that answers: "If I am standing HERE and I step THIS way, how good is that in the long run?"

We name that number $Q(s,a)$.

• $s$ (state) = which square the robot stands on — a situation.
• $a$ (action) = which way it steps — a choice.
• $Q$ = the quality of making choice $a$ in situation $s$.

WHY a number per (situation, choice)? Because "how good is this square" alone isn't enough — the square is only as good as the move you make from it. A square next to a cliff is fine if you step away, deadly if you step off. So goodness lives on the pair (square, move), not the square alone.

PICTURE. The robot on square $s$, four arrows leaving it, each arrow labelled with its own $Q$ value. The move we're scoring is the red one.

---

Step 2 — "In the long run" needs a ruler: the discount $\gamma$

WHAT. "Reward collected forever" could be an infinite pile of numbers. We tame it by making future rewards count a little less than present ones. Each step into the future, we multiply the reward by a shrink factor $\gamma$ (Greek "gamma"), a number between $0$ and $1$.

$$\text{value}=r_0+\underset{\text{1 step away}}{\underbrace{\gamma }}{r}_1+\underset{\text{2 steps}}{\underbrace{{\gamma }^2}}{r}_2+\underset{\text{3 steps}}{\underbrace{{\gamma }^3}}{r}_3+\cdots$$

• $r_0$ = reward right now, counted fully (multiplied by ${\gamma }^0=1$).
• $\gamma r_1$ = next reward, shrunk once.
• ${\gamma }^2{r}_2$ = two steps out, shrunk twice — and so on.

WHY shrink at all? Two reasons, one mathematical, one human. Mathematical: if $\gamma <1$ the infinite sum stays finite (it's a geometric series), so $Q$ is always a real number. Human: a reward today is worth more than the same reward in a hundred steps — impatience is built in.

PICTURE. A row of future rewards, each drawn shorter than the last because ${\gamma }^k$ shrinks them; the red bar is the full-height now reward.

---

Step 3 — The recursion: value of here hides the value of there

WHAT. Look again at that long sum. Group everything after the first reward:

$$Q(s,a)=r_0+\gamma (r_1+\gamma r_2+{\gamma }^2{r}_3+\cdots )$$

The bracket is exactly the same kind of thing we started with — the total future value, but starting from the next square $s^{\prime }$. So the long sum folds up into one short line:

$$Q(s,a)=\underset{\text{reward for this one step}}{\underbrace{r}}+\gamma \cdot \underset{\text{the whole tail, folded}}{\underbrace{(\text{value of the next square }{s}^{\prime })}}$$

WHY fold it? Because we can never sum infinitely many terms by hand. But we can peel off one term and point at the rest. This trick — "value here = reward now + shrunk value of next" — is the Bellman idea, the backbone of all of TD learning.

PICTURE. Two squares linked by the red action arrow: current $s$ carries an immediate reward $r$; next square $s^{\prime }$ carries a "folded" blob standing for all remaining future value.

---

Step 4 — Which value of the next square? Take the best move: $\max$

WHAT. The "value of the next square $s^{\prime }$" is still ambiguous — value doing which move next? Since we want the robot to eventually behave optimally, we assume that from $s^{\prime }$ it will pick the best available move. The tool for "pick the biggest of a set" is $\max$.

$$Q^{\ast }(s,a)=r+\gamma \underset{\begin{array}{c}\text{look at every move }{a}^{\prime }\text{ from }{s}^{\prime },\\ \text{keep the largest }Q\end{array}}{\underbrace{\underset{a^{\prime }}{\max }{Q}^{\ast }(s^{\prime },a^{\prime })}}$$

• ${\max }_{a^{\prime }}$ = "scan over all next-actions $a^{\prime }$, return the biggest value."
• The little star $Q^{\ast }$ means "the optimal Q" — the true goodness once we act perfectly.

WHY $\max$ and not average, and not the action we actually take? Because we're defining the value of ideal play. Ideal play never picks a worse move when a better one exists. This single $\max$ is what makes Q-learning learn the optimal policy even while the robot wanders randomly — the hallmark that separates it from SARSA (which uses the move actually taken).

PICTURE. At $s^{\prime }$, four candidate arrows with $Q$ values $\{3,7,1,5\}$; the red one ($7$) is selected by $\max$ and fed back as the next square's value.

---

Step 5 — We don't have the rulebook, so we sample

WHAT. The clean equation above secretly hides an average over all possible next squares (the world may be random). We don't know those odds. So instead of computing the average, we just try it once: take action $a$, and see what the world actually hands us — one concrete reward $r$ and one concrete next square $s^{\prime }$.

$$\underset{\text{the "target": one honest sample of what }Q(s,a)\text{ should be}}{\underbrace{r+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime })}}$$

WHY sampling? This is what "model-free" means: no map, no probabilities. We learn purely from lived experience $(s,a,r,s^{\prime })$. That's why the same algorithm runs on Atari and robots where nobody can write the world's rulebook.

PICTURE. A slot machine of possible next squares; a single lever-pull lands on one red outcome $s^{\prime }$ — our one sample.

---

Step 6 — One sample is noisy, so nudge, don't replace: the learning rate $\alpha$ and the TD error $\delta$

WHAT. Our current stored guess is $Q(s,a)$. Our fresh sample says it should be the target. First, name the gap between them the TD error $\delta$ (Greek "delta"):

$$\delta =\underset{\text{target}}{\underbrace{r+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime })}}-\underset{\text{old guess}}{\underbrace{Q(s,a)}}$$

• $\delta >0$: things went better than our stored guess expected.
• $\delta <0$: things went worse.
• $\delta =0$: our guess was already spot-on — nothing to learn here.

Now, if we trusted one noisy sample completely we'd overreact. Instead, take a small step of size $\alpha$ along that surprise:

$$Q(s,a)\leftarrow Q(s,a)+\alpha \underset{\text{the surprise}}{\underbrace{\delta }}=Q(s,a)+\alpha [r+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime })-Q(s,a)]$$

Decoding every piece, right where it sits:

• $\leftarrow$ = "replace the left with the right" (an update, not an equation).
• $\delta$ = the TD error we just defined — how surprised were we?
• $\alpha$ (learning rate, $0<\alpha \le 1$) = how far along that surprise we travel. Small $\alpha$ = cautious averaging; $\alpha =1$ = overwrite completely.

WHY a fraction $\alpha$? Because the target jiggles from sample to sample. Nudging a little each time silently averages many samples, smoothing the noise — like slowly zeroing in rather than teleporting to each new rumour.

PICTURE. A number line: the old guess on the left, the target on the right, and a red arrow stepping a fraction $\alpha$ of the gap. The gap itself is $\delta$.

---

Step 7 — Edge cases: terminal states, $\gamma =0$, and $\gamma =1$

WHAT. Four corners the reader will eventually hit, each breaking the general picture in its own predictable way:

1. Terminal (goal) state. When the episode ends there is no next square, so its future value is defined as $0$. The update collapses to

$$Q(s,a)\leftarrow Q(s,a)+\alpha [r-Q(s,a)]$$

— pure reward, nothing folded in. This is the seed: the true reward first enters the system only through terminal transitions, then spreads backward.

2. $\gamma =0$. The whole future term vanishes: $Q(s,a)\leftarrow Q(s,a)+\alpha [r-Q(s,a)]$. The robot becomes utterly short-sighted, chasing only the immediate reward.

3. $\gamma =1$ (no discounting). Now future rewards are counted at full height forever. In a never-ending task the sum $r_0+r_1+r_2+\cdots$ can grow without bound — $Q$ diverges and the geometric-series trick of Step 2 no longer converges. So $\gamma =1$ is only safe for episodic tasks (every run is guaranteed to hit a terminal state in finite time), where the reward pile is a finite sum. Our grid world is episodic, so $\gamma =1$ would be legal there; a robot balancing forever needs $\gamma <1$ or it explodes.

4. $\alpha =1$ vs $\alpha \to 0$. At $\alpha =1$ the old guess is thrown away entirely each step (fast but jittery). As $\alpha \to 0$ the robot stops learning (frozen). Real training lives between.

WHY show these? Because a reader who has met all four corners is never ambushed — not by "why is my goal square value exactly the reward?", not by "why did my undiscounted $Q$ blow up to infinity?"

PICTURE. Three mini-panels: a terminal square with its folded-blob crossed out (red), a $\gamma =0$ arrow with the future greyed away, and an $\alpha$ slider from frozen to jittery.

---

Step 8 — Watch a reward crawl backward (the payoff)

WHAT. Trace the parent note's grid. Reward: $-1$ per step, $+10$ at the goal, $\gamma =0.9$, $\alpha =0.1$, and every $Q$ starts at $0$. We follow the single pair $Q((2,1),\text{right})$ — the square just left of the goal — across the first few times the robot happens to step through it.

First visit (old $Q=0$, since all $Q$ start at $0$):

$$\text{target}=\underset{r}{\underbrace{-1}}+\underset{\gamma }{\underbrace{0.9}}\cdot \underset{\max Q\text{ at goal}}{\underbrace{10}}=8.0Q\leftarrow 0+0.1[8.0-0]=0.8$$

Second visit (old $Q=0.8$ from last time; goal still worth $10$):

$$Q\leftarrow 0.8+0.1[8.0-0.8]=1.52$$

Third visit (old $Q=1.52$):

$$Q\leftarrow 1.52+0.1[8.0-1.52]=2.168$$

Each visit closes $10\%$ of the remaining gap to $8.0$, so $Q((2,1),\text{right})$ climbs $0\to 0.8\to 1.52\to 2.168\to \cdots \to 8.0$. No mystery starting value — every number is derived from the one before it, all the way back to the honest $0$.

WHY it matters. Once $(2,1)$ knows it is worth something, the square before it samples its value and lights up too. Step by step the $+10$ flows upstream against the direction of motion — value is not designed, it seeps backward from wherever reward lives.

PICTURE. The grid across episodes: the goal glows, then its neighbour, then the next — a red wave of value spreading backward toward the start.

---

The one-picture summary

Everything above is one loop: sample a transition → compute the TD error $\delta$ → nudge $Q$ by $\alpha \delta$ → the goal's value seeps backward. This is the picture to keep — the five circled stages are exactly the five arrows you just walked through, closed into a cycle you repeat forever.

Recall Feynman retelling — say it like a story

I'm a robot on a square. I want one number per (square, move) telling me how good that move is in the long run — call it $Q$. "Long run" would be an endless pile of rewards, so I shrink each future one by $\gamma$; that keeps the pile finite (unless $\gamma =1$, which only survives in tasks that always end) and makes me a bit impatient. That endless pile has a beautiful shortcut: value-of-here equals reward-now plus $\gamma$ times value-of-the-next-square. Since I want to end up playing perfectly, I assume from the next square I'll pick my best move — that's the $\max$, and it's why I learn the optimal plan even while wandering. But I have no map, so I can't average over all possible next squares; I just try it once and see the reward $r$ and next square $s^{\prime }$ the world hands me. One try is noisy, so I measure my surprise $\delta$ (the TD error) and step a small fraction $\alpha$ along it — not overwrite. Special cases: at the goal there's no future, so I just soak up the raw reward — and that's the spark. Each visit, that spark of value creeps one square backward, until eventually the very first square knows the shortest path home.

Recall Quick self-test

What does ${\max }_{a^{\prime }}$ make Q-learning learn, and why is that off-policy? ::: It makes the target use the best next action, so $Q$ converges to the optimal values even though the robot may be exploring randomly — the learned target ignores the actual (possibly suboptimal) action taken. That's the off-policy hallmark separating it from SARSA. In the terminal-state update, what happened to the $\gamma \max Q$ term? ::: It's dropped (set to 0) because there is no next state — the update becomes $Q\leftarrow Q+\alpha [r-Q]$, pure reward. Why can $\gamma =1$ be dangerous, and when is it safe? ::: Undiscounted, an unending task sums infinitely many rewards and $Q$ can diverge; it is only safe for episodic tasks that always reach a terminal state in finite time. Write the TD error $\delta$ and the update in terms of it. ::: $\delta =r+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })-Q(s,a)$, and $Q(s,a)\leftarrow Q(s,a)+\alpha \delta$.

Where to go next: the overestimation caused by that $\max$ is fixed in Double Q-learning; scaling $Q$ to huge state spaces needs Function Approximation and Deep Q-Networks (DQN), sped up by Prioritized Experience Replay. The exploration that guarantees convergence is the Exploration-Exploitation Trade-off over an MDP.