Q-learning
What if the agent doesn't know how its world works? It can still learn what each action is worth, one experience at a time: after every step, nudge one number in a table towards "the reward I just got plus the best I think I can do from here".
Kind: learning agent (model-free reinforcement learning).
Week: 4 (slides 30 to 40).
Book: not in Wooldridge (he leaves learning out on purpose). Sutton and Barto 6.5, Russell and Norvig 22.3.
Techniques on this page: the update rule, the TD error and learning rate, off-policy learning, bootstrapping, credit assignment.
The problem it solves
Value iteration needs \(P\) and \(R\). Often nobody has them: how exactly does this robot slip on this floor? What does this game do internally? The agent can only act and see what happens.
Reinforcement learning learns behaviour from experience instead of having it specified in advance. Q-learning (Watkins and Dayan 1992) is the classic model-free method: it never estimates \(P\) at all. It learns \(Q(s, a)\) directly, and since \(\pi^*(s) = \arg\max_a Q^*(s, a)\) is a table lookup, that’s all it needs.
| uses | computes | |
|---|---|---|
| planning | known \(P\), \(R\); sweeps the whole model | \(V^*\), \(Q^*\), \(\pi^*\) |
| model-based RL | learns \(P\), \(R\) from data, then plans | same |
| model-free RL | only samples \((s, a, r, s')\) | \(Q\) directly |
Words you’ll hear
| Word or symbol | Plain meaning |
|---|---|
| transition \((s_t, a_t, r_{t+1}, s_{t+1})\) | one experience: where I was, what I did, what I got, where I ended up |
| Q-table | one number per (state, action) pair |
| target | \(r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a')\): a one-sample guess at what \(Q(s_t, a_t)\) should be |
| TD error \(\delta\) | target minus current estimate: the surprise |
| learning rate \(\alpha\) | how far to move towards the target each time |
| \(\leftarrow\) | assignment, as in code (not an equation) |
| off-policy | learns about the greedy policy while behaving differently |
| bootstrapping | updating an estimate using other estimates |
| credit assignment | which earlier action deserves credit for a later reward? |
Technique 1: the update rule
Problem it solves: learns \(Q^*\) from samples instead of from \(P\).
The Bellman target needs an average over next states. Instead, use the one next state that actually happened as a noisy sample, and move a little way towards it:
\[Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha\big[r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a') - Q(s_t, a_t)\big]\]
In code: Q[s,a] = Q[s,a] + alpha * (target - Q[s,a]). new = old + α(target − old). If \(s_{t+1}\) is terminal, the max is 0. One table entry changes per step.
Worked example (slides 36 to 37). The corridor (\(s_1 \leftrightarrow s_2 \to s_3\), −0.1 per step, 0.9 into the goal), \(Q = 0\) everywhere, \(\alpha = 0.5\), \(\gamma = 0.9\). Exact values (the slides round):
| Experience | Target | \(\delta\) | New value |
|---|---|---|---|
| \((s_2, E, 0.9, s_3)\) | 0.9 | 0.9 | \(Q(s_2, E) = 0.45\) |
| \((s_1, E, -0.1, s_2)\) | \(-0.1 + 0.9(0.45) = 0.305\) | 0.305 | \(Q(s_1, E) = 0.1525\) |
| \((s_2, E, 0.9, s_3)\) | 0.9 | 0.45 | \(Q(s_2, E) = 0.675\) |
| \((s_1, E, -0.1, s_2)\) | \(-0.1 + 0.9(0.675) = 0.5075\) | 0.355 | \(Q(s_1, E) = 0.330\) |
| \((s_2, W, -0.1, s_1)\) | \(-0.1 + 0.9(0.330) = 0.197\) | 0.197 | \(Q(s_2, W) = 0.0985\) |
Heading towards \(Q^*\) = 0.9, 0.71 and 0.539, and East already looks better than West. No \(P\) anywhere.
Technique 2: the TD error and the learning rate
Problem it solves: says how surprised to be, and how much to change.
\(\delta_t = \text{target} - Q(s_t, a_t)\): the difference between two estimates of the same thing, one made before the step and one made after seeing a real reward (slide 34). \(\delta > 0\): better than expected, Q goes up. \(\delta < 0\): worse, Q goes down.
\(\alpha \in (0, 1]\): \(\alpha = 1\) jumps straight to the target (fine if the world is deterministic); a small \(\alpha\) averages over many noisy samples. With \(\alpha = 1/n\) on the \(n\)th visit, \(Q\) is exactly the average of the targets so far.
Worked example. \(Q(s, a) = 2\), \(\alpha = 0.1\), \(\gamma = 0.9\), \(r = 1\), best next value 3. Target \(= 1 + 2.7 = 3.7\); \(\delta = 1.7\); new \(Q = 2.17\). If \(s'\) were terminal: target 1, \(\delta = -1\), new \(Q = 1.9\).
Technique 3: off-policy learning
Problem it solves: lets the agent explore without spoiling what it learns.
The target uses \(\max_{a'}\), the best next action, whatever the agent actually does next. So Q-learning learns the values of the greedy policy even while it behaves differently, e.g. exploring at random (slide 35). Exploratory steps aren’t wasted. Under mild conditions it converges to \(Q^*\) without ever learning \(P\).
(Not on the slides: SARSA uses the action actually taken next, so it learns the policy it’s following: on-policy.)
Technique 4: bootstrapping
Problem it solves: learns online, one step at a time, without waiting for the episode to end.
The target contains \(\max_{a'} Q(s_{t+1}, a')\), the agent’s own current guess. Building estimates on estimates is bootstrapping (slide 38). Powerful (online, incremental), risky (early errors get copied).
The epistemic-bubble discussion (slide 39). Is this like an LLM building on its own possibly-hallucinated earlier step? Similar: beliefs built on unverified beliefs. Different: every Q-learning target contains a real reward and a real next state, and \(\gamma\) shrinks the bootstrapped part, so in the tabular case it’s guaranteed to self-correct eventually. An LLM chain of thought gets no outside signal unless you add one (tool results, tests): that’s what ReAct-style agents do. With neural networks (topic 5), bootstrapping can genuinely diverge.
Technique 5: credit assignment
Problem it solves: a reward at the end must reach the decisions that caused it.
The corridor’s +1 only appears on entering \(s_3\), but it should make East at \(s_1\) look good (slide 40). Each update passes value back one step, so over repeated experience the credit travels backwards, just as it did across value iteration’s sweeps.
Order matters. The slides’ example updates \(s_2\) before \(s_1\), so news travels fast. In real episodes the agent visits \(s_1\) first, while \(Q(s_2, E)\) is still 0, so the goal’s value takes about one episode per step to travel back.
What to read
| Source | Read? | Why |
|---|---|---|
| Wooldridge | Not covered | no learning in the book |
| Sutton and Barto 6.5 (free online) | Optional | Q-learning, with the cliff-walking example contrasting SARSA |
| Russell and Norvig 22.3 | Optional | active RL and Q-learning |
Practice prompt
I'm studying CS5940 Intelligent Agents, week 4 (MDPs and reinforcement learning). I want practice on Q-LEARNING:
- planning vs model-based vs model-free learning
- applying the update Q(s,a) <- Q(s,a) + alpha [r + gamma max_a' Q(s',a') - Q(s,a)] by hand, including terminal next states
- computing the target and the TD error, and what positive or negative delta means
- the effect of the learning rate alpha (alpha = 1 vs small alpha)
- tracing several updates on a 3-state corridor with deterministic moves
- off-policy learning, bootstrapping and credit assignment, in words and with examples
Please:
1. Use plain, everyday language and explain any symbol in one short sentence.
2. Give me ONE question at a time, easy first, then harder, with friendly numbers.
3. Wait for my answer, then mark it and show the full working.
4. If I get it wrong, explain the mistake and give me a similar question.
5. Every 5 questions, summarise my strengths and what to practise.