RL 8：Q-Learning、無模型學習的突破與 off-policy 核心思路（1988–1994）

In Blog 7 we watched Sutton teach machines to predict: chase a moving target of better and better value estimates, and the estimates settle down on the truth. That was a big deal. But there was a catch.

Prediction without action is a weather forecast you can't do anything about.

Knowing "this situation is worth 8 points" is nice. Knowing "so I should turn left" is what actually wins games. This post is about the five years (1988–1994) when RL went from predicting to deciding, and did it without ever being handed a map of the world.

By the end of this post you'll be able to explain, in plain words:

• why "knowing how good a state is" isn't enough to act
• what Q-Learning does and why it was a breakthrough
• what on-policy and off-policy mean (the most important vocabulary split in RL)
• why the fastest route along a cliff edge can be the wrong thing to learn

Quick refresher (and four new words)

Blog 7 already covered state, action, reward, policy, return, value, the discount γ, bootstrapping and the TD error δ, so I won't re-explain them here. If any feel fuzzy, a quick skim of Blog 7 will set you up. Four words show up in this post that are new:

The gap: knowing the score vs knowing the move

Blog 7's value function V(s) answers "how good is it to be here?" That's the exact gap: it scores places, not moves.

Now suppose you're standing at a crossroads and you know:

• the road left leads to a town worth 7
• the road right leads to a town worth 9

Easy, go right. But notice what you needed: you had to know where each road leads. That's the model, the map: P(s' | s, a), the probability of landing in s' after doing a in s.

In a board game with clean rules, you can write that map by hand. In a robot's kitchen, a stock market, or a video game you've never seen? Nobody hands you the map. And building one is often harder than the original problem.

The fix, in one sentence: stop scoring places and start scoring choices.

If you know "taking road right from this junction is worth 9," you don't need to know where it goes. You just pick the best-scoring choice. Algorithms that work this way, without a map of the world, are called model-free.

Three ideas, arriving between 1988 and 1994, made that practical. We'll take them in order.

Idea 1: TD(λ), a dial between "impatient" and "patient" (Sutton, 1988)

Technically this one is still about prediction, so why is it here? Because it upgrades the credit-assignment machinery from Blog 7, and Watkins is about to reuse that machinery for choosing actions.

Blog 7 left you with two separate tools: TD(0) (update from the very next state) and Monte Carlo (wait for the whole episode, then update). Sutton's 1988 paper, Learning to Predict by the Methods of Temporal Differences, showed they're not two tools at all. They're the two ends of one dial.

The dial is λ (lambda), a number from 0 to 1. At λ = 0 you get TD(0). At λ = 1 you get (roughly) Monte Carlo. Everything in between is a blend.

How the dial works: eligibility traces. Think of breadcrumbs. Every state you visit gets a breadcrumb, and the crumbs fade as time passes:

et(s)=γλ et−1(s)+1[St=s]

In words: "a state's crumb fades by a factor of γλ each step, and gets topped up whenever you visit it."

When a surprise arrives (the TD error δ from Blog 7), it gets spread backward along the breadcrumb trail. Fresh crumbs get a big share of the credit. Faded ones get a little.

V(s)←V(s)+α⋅δt⋅et(s)

The eligibility trace idea has roots in Klopf's biological thinking from Blog 6. Sutton turned it into a precise, tunable tool.

Why it matters for what comes next: TD(λ) gives RL its credit-assignment machinery. Watkins would soon bolt the same trick onto action-learning (his version is called Q(λ)). But first he needed to solve the bigger problem: learning actions at all.

Idea 2: Q-Learning, scoring choices instead of places (Watkins, 1989)

Chris Watkins introduced Q-Learning in his 1989 Cambridge PhD thesis, Learning from Delayed Rewards. The idea sounds almost too simple to be a breakthrough.

Instead of V(s) (how good is this state?), learn Q(s, a) (how good is this action in this state?). The "Q" stands for "quality."

Formally, Q*(s, a) is the total future reward you'd expect if you take action a in state s and play perfectly from then on:

Q(s,a)=E[Rt+1+γmax⁡a′Q(St+1,a′)  |  St=s,At=a]

That's Bellman's optimality idea from Blog 3, rewritten for actions. And here's the payoff: once you have Q*, the best policy is trivial. In every state, pick the action with the highest Q. No map required.

The table

Picture a spreadsheet. One row per state, one column per action. Each cell holds the agent's current guess for "how good is this action here?" At the start, every cell is 0 (or random). The agent knows nothing.

The update rule

Every time the agent takes a step, it fixes one cell of the table:

Q(st,at)←Q(st,at)+α[rt+1+γmax⁡a′Q(st+1,a′)−Q(st,at)]

Let's unpack it piece by piece:

• Q(s_t, a_t) is the old guess for this action.
• r_{t+1} is the reward the agent actually got.
• γ max Q(s_{t+1}, a') is the best the next state can offer, discounted. (Bootstrapping again, just as in Blog 7.)
• r + γ max Q(...) together form the target: "what this action looks like now that I've seen what happened."
• The bracket is the TD error: target minus old guess. How wrong was I?
• α is the learning rate: how much of the error to correct per step.

A worked example (with actual numbers)

Say the agent stands in state A and takes action "right," landing in state B.

• Old guess: Q(A, right) = 0
• Reward for the step: r = 0
• Best option in B: max Q(B, ·) = 10 (it already learned that B is next to the goal)
• γ = 0.9, α = 0.5

The target is 0 + 0.9 × 10 = 9. The error is 9 − 0 = 9. The update is 0 + 0.5 × 9 = 4.5.

So Q(A, right) jumps from 0 to 4.5, even though the agent got zero reward on that step. It earned that credit because it led somewhere good.

Now repeat this for thousands of steps. The goal's reward leaks into the square next to it, then into the square next to that, then the next, the same backward-spreading "rumor" from Blog 7's 3-step robot, only now it travels through action scores. Eventually every cell holds a sensible number and the best move from anywhere is "follow the biggest number."

The guarantee

Here's the part that made people sit up. Q-Learning isn't just "usually works." It has a proof.

Watkins outlined it in his thesis, and Watkins and Dayan published the full proof in 1992 (Machine Learning journal, "Technical Note: Q-Learning"). The result: with a table of values, and every action tried repeatedly in every state, Q-Learning converges to the optimal action-values with probability 1. Later, Tsitsiklis (1994) and Jaakkola et al. (1994) re-proved it with a more general toolkit.

The fine print matters, and it'll matter later in this post:

1. Every (state, action) pair must keep getting visited (so you must explore)
2. The learning rate α must shrink at the right pace over time
3. The values are stored in a table, not squeezed into a function approximator

Exploring: how does the agent visit everything?

Condition #1 above hides a puzzle. If the agent always picks its current best-looking action, it'll never discover that the road it dismissed early on was actually great. That's the explore vs exploit tension, one we've met before: Samuel wrestled with it in checkers (Blog 4) and Tsetlin built it into his learning automata (Blog 5).

The simplest practical recipe is ε-greedy:

at={random actionwith probability ε arg⁡max⁡aQ(st,a)with probability 1−ε

Roll a die. Most of the time (say 90%), do what the table says is best. The rest of the time (10%), do something random, just to see. Early in training, ε is large; as the table gets trustworthy, ε shrinks.

Hold on to this one detail, because it sets up the whole second half of the post: while exploring, the agent sometimes does dumb things on purpose.

The quiet superpower: off-policy learning

Look back at the Q-Learning update. The target uses max Q(s_{t+1}, a'): the value of the best next action. But what did the agent actually do next? Maybe it explored and did something random. The update doesn't care. It always learns as if the agent will play perfectly from the next step on.

This means two different "policies" are in play:

• Behavior policy: what the agent actually does while collecting experience (messy, exploratory)
• Target policy: what the agent is learning about (the greedy, best-possible policy)

When these two are different, the algorithm is called off-policy. Q-Learning is the classic example.

An analogy: imagine learning to drive by studying dashcam footage of other people, including clumsy drivers. You can still extract "what's the ideal move at this intersection?" from footage of someone who wasn't playing ideally. That's off-policy. On-policy would be learning to drive only from your own hands-on driving and judging yourself on exactly how you drive.

Why this matters in practice:

• Reuse old data. Experience collected yesterday under a worse policy is still valid for updating Q today.
• Explore wildly without poisoning what you're learning.
• Learn from other people. A human demo, a different bot's game logs: all usable.

This one property is the reason the deep RL systems of the 2010s could store millions of past game frames and keep learning from them. Remember it when we reach DQN.

The table's fatal flaw

Q-Learning worked beautifully on small worlds: grid mazes, toy problems, dozens or hundreds of states. Then people tried it on something real.

Take an Atari game. The "state" is the screen: 210×160 pixels, each with one of 128 possible colors. The number of possible screens is beyond astronomical. You can't build a table with a row for each. You couldn't even store it.

This is the curse of dimensionality from Bellman's era (Blog 3), coming back for revenge. And the fine print from earlier bites: Watkins & Dayan's guarantee covers tables. Swap in a function approximator and the proof no longer applies (and, as people found, training can get unstable).

The natural fix: don't store a row per state. Learn a function that takes any state and estimates its Q-values, generalizing from states it has seen to ones it hasn't. A neural network is exactly that kind of function. Replace the table with a network that outputs one Q-value per action, keep Watkins's update rule almost unchanged, and you get the Deep Q-Network (DQN). That's DeepMind's 2013 breakthrough, and the star of Blog 11.

The table was never the destination. It was the prototype.

Before we get there: Blog 9 takes a detour to 1992, when Gerald Tesauro mixed TD learning with a neural network on a board game. It worked remarkably well, and it happened two decades before DQN.

Idea 3: SARSA, when being realistic beats being optimistic (Rummery & Niranjan, 1994)

By the early 90s, Q-Learning looked great. Then researchers noticed something uncomfortable: it's an optimist.

Its update assumes that after this step, the agent will always make the best possible move. But during training, the agent explores. It stumbles on purpose, on a schedule (remember ε). Q-Learning learns as if those stumbles will never happen.

Most of the time that's harmless. Sometimes it's a disaster. Enter the cliff.

The cliff-walking problem

This is a classic from Sutton & Barto's textbook. A grid, a start square, a goal square, and between them a row of cliff squares. Every step costs -1. Stepping on the cliff costs -100 and sends you back to the start.

The shortest path hugs the cliff edge. If you never slip, it's the best route.

• Q-Learning correctly figures this out: the edge path is the optimal path for a perfect agent. So it learns to walk along the edge.
• But the agent is still doing ε-greedy exploration while it learns. Occasionally it takes a random step... off the cliff. Ouch, -100. Q-Learning logs the penalty, but its update rule still says "the best move from here is great," so it keeps hugging the edge and keeps falling during training.

The SARSA fix

Gavin Rummery and Mahesan Niranjan (Cambridge, 1994) proposed a small change with a big consequence: learn from what the agent actually does next, not from what it could ideally do.

Compare the two updates. Only one term changes:

Q-Learning:Q(st,at)←Q(st,at)+α[rt+1+γ max⁡a′Q(st+1,a′)⏟best possible next action−Q(st,at)]

SARSA:Q(st,at)←Q(st,at)+α[rt+1+γ Q(st+1,at+1)⏟action actually taken−Q(st,at)]

Because each update needs the five things State, Action, Reward, next State, next Action, the algorithm is called SARSA.

What SARSA does on the cliff: when it wobbles near the edge and falls, the next-action value it bootstraps from is the real, wobbly one, so the penalty drags down the value of walking near the edge. Over time it prefers a longer, safer path with a buffer from the cliff. Not because that path is theoretically shortest, but because it's the best path for an agent that sometimes makes random moves.

This makes SARSA on-policy: the policy being learned and the policy generating experience are the same thing.

So which one is "better"?

Open Google Colab Notebook : QLearning vs SARSA Cliff Problem

Neither. They answer different questions:

Two honest footnotes so nobody gets the wrong idea:

• Q-Learning's final greedy policy really is the optimal one. The edge path is shortest. Its problem is the cost it pays during training, not the policy it ends up with.
• SARSA isn't permanently stuck being cautious. If you shrink ε toward zero as training goes on, SARSA's behavior and Q-Learning's converge on the same optimal policy. SARSA is cautious because of exploration, not by nature.

The divide that never went away

Q-Learning vs SARSA looks like a niche algorithm detail. It turned out to be one of the big forks in the road of all of RL:

Off-policy (Q-Learning, DQN, SAC): learn about the best policy regardless of how you collected the data. Superpower: you can recycle old experience, which makes learning sample-efficient. Cost: learning can be less stable, especially once neural networks get involved.

On-policy (SARSA, PPO, most policy-gradient methods): learn only from data produced by your current behavior. Superpower: updates are consistent with what the agent really does, which tends to be more stable. Cost: you have to throw data away after you use it, so it's less sample-efficient.

You'll see both camps again. PPO, an on-policy method, became the workhorse for fine-tuning large language models with human feedback (RLHF). DQN-style and SAC-style methods, off-policy, dominate where interaction with the world is expensive. Many of today's design debates in RL are really the same question Watkins and Rummery put on the table: do I learn about what I could do, or about what I actually do?

What 1988–1994 actually established

Three things that weren't true in 1987 but were by 1994:

1. A machine can learn good behavior without a map of its world. Given a small enough problem (one a table can hold), Q-Learning learns the optimal policy purely from trial and error, with no transition model, and Watkins and Dayan proved it.

2. How you explore is a design choice, not a side effect. Learn about the ideal (Q-Learning, off-policy) or learn about reality (SARSA, on-policy). Both are useful, and the choice shapes everything downstream.

3. The Q-table is just a function approximator in its simplest form. Swap the table for something that generalizes, and the same update rule keeps working. The theory was already pointing at DQN, twenty years early.

What was missing was the generalizing part. Tables collapse at scale, and neural networks were the obvious replacement, but training them with TD updates turned out to be surprisingly unstable. That problem stayed open for a long time.

Next up: a neural network teaches itself backgammon

While theory was getting tidy, one researcher quietly tried the "obviously unstable" thing anyway. In 1992, Gerald Tesauro paired a neural network with TD learning and had it play backgammon against itself, millions of times, with no hand-written strategy. It reached a level that rivaled the world's best human players.

TD-Gammon was the first big proof that neural networks and RL could work together at scale. It also made self-play a training paradigm, the same idea that eventually leads to AlphaGo, AlphaZero, and beyond.

That's Blog 9.

Quick recap (if you only read this)

• Model-free = learn what to do without learning how the world works.
• TD(λ) = a dial between impatient and patient learning; breadcrumbs (eligibility traces) spread credit backward.
• Q-Learning = score choices, not places; guaranteed to converge for tables; off-policy.
• SARSA = learn from what you actually do; on-policy; safer when exploring is risky.
• The table breaks at scale, which sets up neural networks.