Reinforcement learning without a model. An agent that never sees the transition table still learns to act optimally — by nudging one action-value toward the reward it got plus the best it believes comes next. Reward at the goal crawls backward, step by step, until every state knows which way to walk. Rendered, not quoted.
A deterministic chain MDP: five states s0..s4, s4 the goal. Two actions — R (move right) and L (move left, clamped at s0). Reward is +1 only on arriving at s4, 0 everywhere else.
The learner is given no map. Each experience is a tuple (s, a, r, s'). It updates one cell of a Q‑table:
Q(s,a) ← Q(s,a) + α[ r + γ·maxa'Q(s',a') − Q(s,a) ]
The bracket is the temporal-difference error. γ=0.9, α=0.5, ε‑greedy exploration (ε=0.3), fixed‑seed PRNG. The bootstrap term γ·maxQ(s') is how future value leaks into the present cell.
Q‑learning is Bellman's dynamic programming (the-dynamic-programming) run from experience instead of a known model.
Bellman needs the full transition matrix to sweep V(s)=maxa[r+γ∑P(s'|s,a)V(s')]. Watkins removes P: sampled transitions are the expectation, and maxa'Q(s',a') replaces the swept value. The Q‑table's fixed point is exactly Bellman's optimality equation — the same Q*, reached without ever writing the model down. Value iteration, done blind.
Re-runs the learner live under the current flags, then checks convergence to Q*, a near‑zero Bellman residual, and an optimal greedy path. Flips red the instant the Red Team's tamper is live.
The learner receives only sampled experience — no transition model, no reward map.
episodes = 3000 · start at s0 · act ε‑greedily · observe (s, a, r, s') · seed 12345.
Live Q‑table (best action shaded). Watch reward propagate back from the goal as you add episodes.
greedy policy —
Converged Q matches the Bellman fixed point Q*; the greedy policy walks s0→s4 in the optimal 4 steps. Proven at boot:
wall Q‑learning's convergence proof leans on assumptions the wall does not honour for free.
Every state–action pair must be visited infinitely often: with pure exploitation and no exploration, the agent can lock onto a wrong action and never sample the right one. The learning rate must satisfy the Robbins–Monro schedule (∑α=∞, ∑α2<∞) — a constant α only converges in a deterministic world like this chain. With function approximation replacing the table, the max operator can make updates diverge (the deadly triad). And the same max makes vanilla Q‑learning systematically overestimate (Hasselt's Double‑Q).
"Q‑learning needs a model of the environment."
→ No. It is model‑free — sampled transitions stand in for the transition matrix.
"It only converges if you follow the greedy policy."
→ No. It is off‑policy: it learns Q* while behaving with any exploratory policy, because the target uses maxa', not the action actually taken.
"A constant learning rate always converges."
→ Only in deterministic problems. Under noise you need decaying α or the estimate never settles.
The disclosed planted void: drop the bootstrap γ·maxQ(s') term so each cell is nudged toward the immediate reward only. Now nothing carries value backward — only Q(s3,R) ever sees the +1, the rest stay 0, and the greedy policy stalls short of the goal. Window 7 catches it live.
bootstrap: intact