Foundations — Q-learning algorithm

Before you can read the parent note Q-learning algorithm, every squiggle in it must feel obvious. This page takes each symbol it uses, gives it a plain-words meaning, ties it to a picture, and says why the topic can't live without it. We go in build order: nothing appears before the thing it rests on.

0. The world we are in: an agent poking at an environment

Everything starts with a loop between two characters.

This loop is the stage. Every symbol below is just a name for one arrow or one box in that picture. This picture is formalised by Markov Decision Processes — but you don't need that page yet; the picture is enough.

1. State — $s$

• Picture: one dot on the grid in the figure above — the agent's current spot.
• Why we need it: the whole point is that the right move depends on where you are. Going "right" is great near the goal and terrible near a wall. Without a name for "where you are", you can't say "the best move here". $s$ is that name.

The set of all possible states is written $S$ (a capital letter for the whole collection). "$s\in S$" is read "$s$ is one of the states in the set $S$". The symbol $\in$ just means "is a member of".

The special state where the episode ends (you reached the goal, you died, time ran out) is called a terminal state. Nothing happens after it.

2. Action — $a$

• Picture: one of the four amber arrows leaving the agent's dot below.
• Why we need it: the agent's only power over the world is which action it picks. Learning "which action is best in each state" is the whole job.

The set of all actions is $A$. "$a^{\prime }$" (read "a-prime") is just a different action — we use the little tick mark whenever we mean "some other action, usually in the next situation". Get comfortable with the prime mark: throughout the topic, plain letters mean "now", primed letters ($s^{\prime }$, $a^{\prime }$) mean "one step later".

3. Reward — $r$ and the reward idea $R$

• Picture: the amber number that pops up on the arrow the agent just followed.
• Why we need it: reward is the only signal telling the agent what we want. No maps, no instructions — just "here's how many points that earned". Everything Q-learning learns, it squeezes out of these numbers.

The parent also writes $R(s,a)$ — the "reward function", the rule that decides the reward. The lowercase $r$ is one observed number from experience; the capital $R(\cdot )$ is the underlying rule that generated it. Q-learning is called model-free precisely because it never learns $R(s,a)$ or the transition rule $P(s^{\prime }|s,a)$ — it only ever uses the sampled $r$ it actually saw.

4. The transition $P(s^{\prime }\mid s,a)$ — the world's hidden dice

• Picture: dashed arrows from your dot to the possible next dots, each with a probability tag; sometimes "right" slips and you go up instead.
• The bar $\mid$ is read "given": "$s^{\prime }$ given $s$ and $a$". It's the notation for "this probability depends on the situation and the move".
• Why we mention it: so we can say the magic: Q-learning never touches $P$. It's hidden dice the agent never gets to see. Instead of computing averages over $P$, Q-learning just plays and watches. Remember this — it's the reason Step 2 of the parent's derivation ("turn expectation into sampling") exists.

5. Return, and why the future is discounted — $\gamma$

The agent doesn't care about one reward; it cares about the total it will collect from now on. Add up all future rewards:

$G=r_1+r_2+r_3+\cdots$

That sum could run forever and blow up to infinity. Also, a reward now should count for more than the same reward in a thousand years. Both problems are fixed by one knob.

$G=r_1+\gamma r_2+{\gamma }^2{r}_3+{\gamma }^3{r}_4+\cdots$

• $\gamma =0$: only the immediate reward matters (short-sighted).
• $\gamma \to 1$: distant rewards matter almost as much as now (far-sighted).
• Why it must be $<1$ for the theory: the same shrinking that tames the sum is exactly what makes the update "contract" toward one answer (see the convergence theorem in the parent). Hold onto that.

6. The Q-value — $Q(s,a)$, the star of the show

Now we can name the thing Q-learning actually stores.

• Picture: a table. One row per state, one column per action, a number in every cell. That grid of numbers is the agent's brain.
• The letter Q stands for "Quality" of a state-action pair. It's not a mysterious symbol — it's a lookup table.
• Why we need it: if you know $Q$, choosing well is trivial — in each state, read the row and pick the biggest number. So learning the whole problem reduces to filling in this table correctly.

The parent writes $Q^{\ast }(s,a)$ (with a star). The star means the optimal values — the true, correct table you'd have if you played perfectly forever. Plain $Q(s,a)$ is the agent's current guess, which starts wrong and creeps toward $Q^{\ast }$.

7. The max — ${\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$

Read this as: "look at the next state $s^{\prime }$, scan across all its actions $a^{\prime }$, and take the biggest Q-value in that row."

• Picture: in the next-state row of the table, put your finger on the tallest bar.
• The subscript $a^{\prime }$ under $\max$ means "the maximisation ranges over all next-actions $a^{\prime }$". The result is a single number: the value of the best thing you could do next.
• Why this exact tool? We want to learn how good it is to act optimally. Optimal play means "in the next state, do the best move" — and "the best move's value" is literally the maximum of that row. That single $\max$ is what makes Q-learning learn the optimal policy even while the agent wanders around randomly. This is the off-policy property. (Its cousin SARSA uses the actual next action instead of the max, which is why SARSA is on-policy.)

The max is also the villain in "Mistake 2" of the parent: taking the max of noisy guesses tends to grab overestimates — the reason Double Q-learning exists.

8. Expectation — $\mathbb{E}[\cdot ]$

• Picture: roll the world's hidden dice a thousand times, record the number each time, take the average.
• Why the topic needs it: the world is random ($P$ from §4). Doing "right" might land you in different next states. $Q(s,a)$ is defined as an average over all those possibilities — hence the $\mathbb{E}$.
• The punchline of the whole algorithm: we can't compute this average, because we can't see $P$. So Q-learning replaces "average over all outcomes" with "the one outcome we just experienced", and repairs the noise by only nudging a little each time. That nudge fraction is our last symbol.

9. Learning rate — $\alpha$ — and the update arrow $\leftarrow$

• Picture: a slider between "old value" and "new target". $\alpha$ tells you how far along the slider to move.
• The arrow $\leftarrow$ in $Q(s,a)\leftarrow \dots$ is assignment: "replace the left value with the right value". It is not an equals sign; it's "update to become".
• Why we need it: one sample is noisy (§8). A small $\alpha$ averages many noisy samples into a steady estimate.

Putting the last four symbols together gives the parent's update rule — and now every piece is earned:

10. The Greek and symbol cheat-sheet

How these feed the topic

Every arrow says "you need the left box before the right box makes sense". The bottom node is the whole parent topic.

Equipment checklist

Cover the right side and test yourself. If any answer is fuzzy, reread that section before opening the parent note.