Q-learning

Q(s, a) is a promise: «if you are in state s, take action a, and then play as well as you can — this is how much you get in total».

At the start every promise is zero, and every one of them is wrong. Every time the agent tries something it corrects one promise:

$Q(s,a) \leftarrow Q(s,a) + \alpha\left[\underbrace{r + \gamma \max_{a'} Q(s',a')}_{\text{a better guess}} - Q(s,a)\right]$

Read it as: I thought Q(s,a). I actually got r, and ended up in s′ where the best I can do is worth max Q(s′,·). So my new guess is r + γ·max Q(s′,·). Move me a little way (α) in that direction.

The expression inside the brackets is called the TD error — the difference between what I thought and what I just learnt. When it is zero everywhere the agent has finished learning.

The remarkable part: the agent never needs to know how the world works. It only needs to try things, see what happens, and correct its promises.

Q-learning is off-policy. The update uses $\max_{a'} Q(s',a')$ — the value of the best next move, not the move the agent will actually make. So the agent learns about the greedy policy while it behaves exploratorily.

That is the difference from SARSA, which uses the action actually taken:

	Update	Learns	Behaves as if
Q-learning	$r + \gamma \max_{a'} Q(s',a')$	the optimal policy	the exploration did not exist
SARSA	$r + \gamma\, Q(s',a')$	the policy it actually follows	the exploration is still there

That gives a concrete difference: if there is a narrow path along a cliff, Q-learning takes the path (optimal if you never slip), while SARSA takes a detour (safer when you occasionally step sideways). Neither is «right» — they answer different questions.

Convergence. Tabular Q-learning converges to $Q^*$ if every (s, a) pair is visited infinitely often and the learning rate decays appropriately ($\sum \alpha_t = \infty$, $\sum \alpha_t^2 < \infty$). In practice a constant $\alpha$ and a shrinking $\varepsilon$ are used.

The hyperparameters and what they do:

	Means	Typically	The symptom when wrong
$\alpha$	how much each experience moves Q	0.1	too high: Q jumps and never converges
$\gamma$	how far ahead the agent sees	0.9–0.99	too low: short-sighted, does not find distant goals
$\varepsilon$	how often it explores	1 → 0.05	too low early: gets stuck on the first solution

The limitation is the table. A chessboard has more states than there are atoms in the solar system, and you cannot store one row per state. That is exactly the gap Deep Q-Networks fill.

import random
from collections import defaultdict

def q_learning(env, episodes=5000, alpha=0.1, gamma=0.95, seed=0):
    Q = defaultdict(float)                     # (state, action) -> value
    rng = random.Random(seed)
    for e in range(episodes):
        eps = max(0.05, 1.0 - e / (0.6 * episodes))
        s, done = env.reset(), False
        while not done:
            actions = env.actions(s)
            if rng.random() < eps:
                a = rng.choice(actions)                                      # explore
            else:
                a = max(actions, key=lambda x: Q[(s, x)])                    # exploit
            s2, r, done = env.step(a)
            best_next = 0.0 if done else max(Q[(s2, x)] for x in env.actions(s2))
            Q[(s, a)] += alpha * (r + gamma * best_next - Q[(s, a)])         # the TD update
            s = s2
    return Q

# Two pitfalls that cost hours if you miss them:
#
# 1. best_next MUST be 0 in a terminal state. Otherwise the agent bootstraps on
#    a value that does not exist, and Q grows without bound.
#
# 2. Q[(s, a)] on a defaultdict CREATES the entry. Use Q.get((s, a), 0.0) when you
#    only want to read, otherwise the table fills up with zeros for everything you
#    have ever looked at.

def greedy_policy(Q, env):
    return {s: max(env.actions(s), key=lambda a: Q.get((s, a), 0.0))
            for s in env.states()}

The two comments are the most common faults in hand-written Q-learning. The first gives Q values growing towards infinity and an agent that appears to be learning but never does; the second gives a silent memory leak in long runs.