Q-Learning

Learn the value of each action from raw experience alone, then act greedily on those values with no model of the world.

Taking a2 for reward 1.0 with best next value 4.0 and discount 0.9 gives target 4.6, and Q(s, a2) moves toward that target

Why Does This Exist?

Real tasks hide their dynamics. You get no transition table $T(s^{\prime} \mid s, a)$ and no reward formula $R(s, a, s^{\prime})$ , only the outcomes of actions you try. Dynamic programming needs the model, so it cannot run here. Q-learning (Watkins 1989, convergence by Watkins and Dayan 1992) learns the optimal action values from experience alone and never asks how the world works.

The trick is bootstrapping off your own estimates plus off policy updating. The agent may wander with epsilon-greedy exploration while its update already aims at the greedy future, so behavior and learning stay decoupled. That split is what lets one table improve toward optimal play while the agent still explores. For the Markov setup underneath, start with MDP foundations. For why the wander matters, read exploration versus exploitation. For pixels and nets instead of tables, go to deep Q-networks.

Think of It Like This

Ranking chess moves by played games, not by tree search

You never memorize the full game tree. You play thousands of blitz games, and after each move you nudge your feeling for that position toward what actually followed plus what your current judgment says the rest was worth. Moves that kept leading to wins climb; moves that kept fizzling sink. Eventually you just play the top ranked move per position.

That running rank is the Q-table, the nudge is the TD error, and playing a random novelty every so often while still ranking everything by best play is the off policy part.

Where it stops: chess has an opponent and a terminal win signal, while Q-learning also handles stochastic rewards, discounts, and continuing tasks with no final whistle. The update by experienced outcome carries over.

How It Actually Works

$Q(s, a)$ estimates expected discounted return from taking action $a$ in state $s$ then acting optimally after. Here $r$ is the immediate reward, $\gamma$ in $[0, 1]$ is the discount that shrinks future value, and $\alpha$ is the step size. The optimal table $Q^{\ast}$ satisfies $Q^{\ast}(s, a) = \mathbb{E}[R + \gamma \max_{a^{\prime}} Q^{\ast}(s^{\prime}, a^{\prime}) \mid s, a]$ . Policy falls out for free: at $s$ , take $\arg\max_a Q(s, a)$ .

The update

After one transition $(s, a, r, s^{\prime})$ , with $s$ state, $a$ taken action, $r$ reward, $s^{\prime}$ next state:

$Q(s, a) \leftarrow Q(s, a) + \alpha \left[r + \gamma \max_{a^{\prime}} Q(s^{\prime}, a^{\prime}) - Q(s, a)\right]$

The bracket is the TD error: target $r + \gamma \max Q(s^{\prime})$ minus current $Q(s, a)$ . Positive means too low, so raise it; negative means too high, so lower it. The $\max$ makes it off policy because the target assumes the greedy next action even when exploration picked something else. Tabular Q-learning converges to $Q^{\ast}$ with probability $1$ when every pair is visited infinitely often and steps satisfy $\sum \alpha_t = \infty$ with $\sum \alpha_t^2$ finite; in practice use small constant $\alpha$ like $0.1$ and anneal exploration toward $0.01$ .

Worked example

State $s$ holds $Q = [1.2, 3.5, 2.1]$ for $[a_1, a_2, a_3]$ . The agent takes $a_2$ (current best is also $a_2$ here, but the rule does not require it), earns $r = 1.0$ , lands in $s^{\prime}$ holding $[0.8, 1.1, 4.0]$ . Best next value is $\max Q(s^{\prime}) = 4.0$ .

With $\gamma = 0.9$ and $\alpha = 0.5$ :

$target = 1.0 + 0.9 \times 4.0 = 1.0 + 3.6 = 4.6$

$error = 4.6 - 3.5 = 1.1$

$Q(s, a_2) \leftarrow 3.5 + 0.5 \times 1.1 = 3.5 + 0.55 = 4.05$

The diagram draws this exact step: $s$ on the left, $s^{\prime}$ on the right with $4.0$ marked MAX, target $4.6$ below, arrow back raising $Q(s, a_2)$ from $3.5$ toward $4.6$ . Repeat across visits and the table climbs to the fixed point where each entry equals its own target.

Code

The snippet recomputes the worked target and update with the standard library only.

1q_current = 3.52reward = 1.03gamma = 0.94next_best = 4.05alpha = 0.56
7target = reward + gamma * next_best8print(round(target, 4))  # -> 4.69
10error = target - q_current11print(round(error, 4))  # -> 1.112
13q_new = q_current + alpha * error14print(round(q_new, 4))  # -> 4.05

The prints match the hand derived target $4.6$ , error $1.1$ , and updated value $4.05$ .

Watch Out For

Max of noisy values runs hot

The target takes $\max_{a^{\prime}} Q(s^{\prime}, a^{\prime})$ over noisy estimates, and maxima of noise sit above the true maximum. That upward bias compounds into overoptimism and unstable jumps, the classic maximization bias.

Split selection from evaluation the Double Q-learning way: pick $a^{\ast}$ with one estimator, score it with another. If values climb early then crash across seeds, suspect the max before touching rewards.

Greedy too early starves the table

Convergence needs every pair visited plenty. Annealing exploration fast strands whole regions at zero visits while the policy already exploits, so the table looks decided but is just sheltered.

Track visit counts per pair and slow the anneal when large areas sit near zero. If late performance swings with the seed, coverage ran out before learning did.

The Quick Version

Q-learning is model free and off policy: experience alone teaches optimal action values.
Update is $Q(s, a) + \alpha [r + \gamma \max Q(s^{\prime}) - Q(s, a)]$ , where the bracket is the TD error.
The $\max$ assumes greedy next play even during random exploration, decoupling behavior from learning.
With $r = 1.0$ , $\gamma = 0.9$ , best next $4.0$ , target is $4.6$ and $Q(s, a_2)$ moves $3.5$ to $4.05$ at $\alpha = 0.5$ .
Tables converge with infinite visits plus decaying steps; pixels need function approximation instead.