When Tables Break — Function Approximation
Tabular Q-learning is beautiful, but it can't scale. To play video games from raw pixels or steer a robot, an agent has to generalize — and that is exactly where neural networks walk into reinforcement learning.
🎯 By the end you'll understand
Why the value tables from Stage 2 hit a wall on real problems, how function approximation replaces the lookup table with a learned function that generalizes across states, why neural networks are the approximator of choice (giving us "Deep RL"), and the honest catch — the deadly triad that can make it diverge.
KEY INSIGHTThe one idea to take away
A table memorizes a value for every state. A function learns a pattern — so visiting a few states teaches the agent about the many it has never seen.
Everything in Stage 2 stored knowledge in a grid: one cell per state (for V(s)) or per state-action pair (for Q(s,a)). That works wonderfully when the cells are few. But the real world has more states than there are atoms in the universe — and you will never visit most of them even once. So we stop memorizing and start generalizing: we fit a function with adjustable parameters θ that maps any state to a value, including states no agent has ever touched.
Tabular RL asks "what did I learn about this exact state?" Function approximation asks "what does the pattern I learned predict for this state?" The first needs to visit every state. The second only needs to see enough to learn the pattern — and then it answers for the rest.
CORE CONCEPTThe wall: just count the states
Back in Lesson 2.6, Q-learning kept a table: rows for states, columns for actions, one number in each cell. The cleaning robot had 3 rooms and a handful of moves — a tiny table you could print on a napkin. The update rule filled in those cells one experience at a time, and it converged beautifully.
Now leave the napkin behind. How big does the table get on a real problem?
| Problem | What a "state" is | Number of states | Table feasible? |
|---|---|---|---|
| Cleaning robot (2.6) | which of 3 rooms | 3 | Trivial |
| Tic-tac-toe | marks on a 3×3 board | ≈ 5,478 legal | Easy |
| Chess | full board position | ≈ 1044 | Hopeless |
| Atari from pixels | one 210×160 screen, 128 colors | 12833,600 | Absurd |
| Robot arm | continuous joint angles & speeds | ∞ (continuous) | Impossible |
Look at the Atari row. A single frame is 210 × 160 = 33,600 pixels, and even at a coarse 128 brightness levels each, the number of distinct screens is 12833,600 — a number with tens of thousands of digits. There is no computer, now or ever, with enough memory for one cell per screen. And the continuous robot arm is literally infinite: between angle 30.0° and 30.1° there are infinitely many positions.
But running out of memory is only half the wall. The deeper problem is experience:
Even if you could store the table, you would only ever fill in the cells you actually visit. In a space of 12833,600 screens, you'll see a vanishingly tiny fraction. Every other cell stays blank — and a tabular agent has nothing to say about a state it hasn't visited. It can't guess. It can't interpolate. The cell is just empty.
This is why tables break. Real problems are too big to store and far too big to visit. We need a method where seeing a few states teaches us something about the rest.
INTUITIONThe fix: learn a pattern, not a list
Imagine I ask you the price of a house you've never seen. You don't have a giant table memorizing every house on Earth — and even if you did, this particular house wouldn't be in it. Instead you've learned a rough formula from a handful of houses: bigger is worth more, a good neighborhood adds value, an extra bathroom helps. Feed in the new house's features and out comes a sensible estimate. You've never seen this house, yet you can price it — because you learned the pattern, not the list.
That is the entire idea of function approximation. Instead of a lookup table, the agent learns a function
where θ ("theta") is a bundle of adjustable numbers — the parameters or weights. We don't store one value per state; we store one (small) set of parameters that describes the whole value surface. Learning means nudging θ so the function's predictions get closer to the targets — the very same TD targets you met in Lesson 2.5, now used to move weights instead of overwriting cells.
Replacing the value table with a parameterized function V̂(s; θ) or Q̂(s,a; θ) whose few parameters θ are tuned from experience. The function returns a value for any input — including states the agent has never seen.
And here's the gift that falls out for free: because the function is smooth in its inputs, similar states get similar values automatically. Learn that one screen is dangerous, and nearby screens — almost the same pixels — inherit a similar low value without ever being visited. That transfer of knowledge from seen states to unseen ones has a name.
When learning about one state automatically improves the agent's estimates for other, similar states. It is the superpower a table can never have — and the reason function approximation scales to enormous and continuous state spaces.
FRAMEWORKFrom features and weights to neural networks
So what is the function? The simplest honest answer is the place to start.
Linear function approximation. Describe each state with a handful of features — numbers you choose that summarize it. For the house: size, bathrooms, neighborhood score. For a robot: position, velocity, distance to goal. Stack them into a vector x(s), give each feature a weight in θ, and the value is just a weighted sum:
This is the leanest approximator there is. It generalizes well, it's fast, and its learning behaves nicely. Its weakness: you have to invent good features by hand. If value depends on some twisty nonlinear combination of pixels, a plain weighted sum can't represent it — and figuring out the right features for raw pixels is a nightmare nobody wants.
Neural networks. A neural network is a far more powerful approximator: a stack of weighted sums with nonlinear "squashing" steps in between, all controlled by parameters θ. Crucially, it doesn't just fit weights to features you supply — given enough layers it learns the features itself, discovering directly from raw pixels which patterns matter (an edge here, an enemy there). You hand it the screen; it figures out the rest.
Use a neural network as the approximator for V or Q, and you have arrived at Deep RL:
# BEFORE — Stage 2: a lookup table, one cell per (state, action) Q = {} # a giant dictionary value = Q[state][action] # blank if never visited ✗ # AFTER — Stage 3: a function with parameters θ value = net(state, action, theta) # returns a value for ANY state ✓ theta = nudge(theta, td_error) # learning tweaks θ, not a cell
The adjustable numbers inside the approximator — feature weights for a linear model, or the connection weights of a neural network. Training adjusts θ; the table of values is gone. A net with a million parameters can describe value over 1044 chess positions.
Reinforcement learning where the function approximator is a deep neural network. Same RL ideas as Stage 2 — states, actions, rewards, value, TD updates — with a neural network doing the value (or policy) estimation so it scales to pixels, sound, and continuous control.
SEE ITTable vs Function
Here is a one-dimensional world: 8 states laid out in a row, and the "true" value rises smoothly from left to right (think: closer to the goal = higher value). The agent has only visited a few of them, marked with a bright outline. Flip the toggle and watch what each method does with the states the agent never saw.
In tabular mode, the unvisited cells read ? — blank, unknown, useless. The agent that lands on one has learned nothing to fall back on. In function mode, the same few visits let the agent fit a smooth line through the gaps: every unseen state gets a reasonable value, close to its neighbors. That is generalization, made visible. Notice the function's estimates aren't perfect — they're a smooth approximation, not the exact truth — but a sensible guess everywhere beats an exact answer almost nowhere.
FORMALThe functions, said precisely
Two estimators, depending on what you want to approximate. The state-value function:
and the action-value function — the one Deep Q-Networks will use next lesson:
Learning no longer overwrites a cell. It measures how wrong the prediction is — the same TD error from Stage 2 — and nudges θ a little in the direction that reduces it, scaled by the learning rate α:
Read it next to the tabular Q-update from 2.6 and the family resemblance is obvious. The bracket is the same TD target minus current estimate. The only change: instead of writing a new number into a cell, we move the parameters, and the ∇θ term says "in the direction that most increases this prediction." Because one update to θ shifts the prediction for many states at once, learning about St ripples out to its neighbors. That ripple is generalization.
WEAKNESSThe cost: the deadly triad
Honesty time. Tabular Q-learning came with a guarantee: under reasonable conditions it converges to the right answer. The moment you swap the table for a function approximator, that guarantee is gone. Worse, three ingredients we genuinely want — and have already been using — can combine into instability so notorious it has a name.
When you mix all three of these at once, value estimates can blow up to infinity instead of converging:
- Function approximation — values are tied together, so an update to one leaks into others.
- Bootstrapping — TD updates a guess from another guess (the maxa Q̂(St+1,a) target is itself an estimate). Errors can feed on themselves.
- Off-policy learning — learning about one policy from data generated by another (Q-learning is off-policy, from 2.6).
Any two of the three are usually fine. It's the combination of all three that can diverge — and Q-learning with a neural network has all three at once. This isn't a reason to give up; it's the reason the next lesson exists. Deep Q-Networks are, at heart, a bag of clever tricks (experience replay, a frozen target network) that tame exactly this triad and make deep Q-learning stable enough to beat humans at Atari.
CONTEXTDeep RL = RL + deep neural networks
If Stage 3 feels like a fresh start, here's the reassurance: it isn't. Everything you built in Stage 2 still stands. The agent still observes states, takes actions, collects rewards, and chases the discounted return. It still learns from TD errors. The Bellman ideas, the exploration–exploitation balance, on- vs off-policy — all unchanged.
The only thing we swapped is where the value lives: out of a table, into a neural network. That single substitution is what "Deep RL" means.
Deep RL = the RL ideas of Stage 2 + a deep neural network as the function approximator. Not a new field — the same field, finally able to handle the real world.
WEAKNESSCommon mistakes to avoid
A bigger table doesn't help when the state space is 12833,600 or literally infinite — you can't store it, and you'd never visit most cells anyway. The problem isn't table size; it's that a table can't generalize. The fix is a different representation, not a roomier one.
It is not guaranteed to converge. Combine it with bootstrapping and off-policy learning — the deadly triad — and value estimates can diverge to infinity. Stability is something we engineer (DQN's tricks), not something we get for free.
No — it's the same RL, with a neural net replacing the table. States, actions, rewards, returns, TD errors, on/off-policy: all carry over unchanged. If you understood Stage 2, you already understand most of Deep RL.
KEY INSIGHTWhere this connects in your course
- Tabular Q-learning (2.6) — the table this lesson retires; the Q-update we just rewrote in terms of parameters θ.
- Value functions (2.3) — V(s) and Q(s,a) are exactly what the approximator now estimates, just with weights instead of cells.
- Deep Q-Networks (3.2) — the next lesson: a neural net for Q, plus the tricks (replay, target network) that tame the deadly triad.
- Policy gradients (3.3) — instead of approximating value, approximate the policy π(a|s; θ) directly — the other great branch of Deep RL.
Hold the one sentence — swap the table for a function that generalizes — and the rest of Stage 3 is just choosing which function, and keeping it stable.
GLOSSARYKey terms introduced
- Function approximation
- Replacing the value table with a parameterized function V̂(s;θ) / Q̂(s,a;θ) tuned from experience; returns a value for any input.
- Generalization
- Learning about one state automatically improving estimates for other similar states — what tables cannot do.
- Parameters (θ)
- The adjustable numbers inside the approximator (feature weights or network weights); training tunes θ.
- Linear approximation
- Value as a weighted sum of hand-chosen features, θ · x(s) — simple and stable, but you must design the features.
- Neural approximation
- A neural network as the approximator; learns its own features from raw input and represents nonlinear value surfaces. The basis of Deep RL.
- Deep RL
- Reinforcement learning using a deep neural network as the function approximator for value or policy.
- Deadly triad
- The combination of function approximation + bootstrapping + off-policy learning, which together can cause value estimates to diverge.
ACTIVE RECALLCheck your understanding
Answer in your own words first, then reveal.
1Why can't tabular Q-learning handle Atari played from pixels?›
A single screen is one state; there are about 12833,600 possible screens — far too many to store one cell each, and you'd visit only a microscopic fraction. Unvisited cells stay blank, so a tabular agent has no value for almost every state it meets.
2What does function approximation give you that a table never can?›
Generalization. Because the function is smooth in its inputs, learning about one state improves estimates for similar, never-visited states. A few visits produce reasonable values everywhere, instead of values for only the visited cells.
3What changes — and what stays the same — when we go from a table to a function for Q?›
Changes: value lives in parameters θ (e.g. a neural net) instead of cells; updates nudge θ rather than overwriting a cell. Stays the same: the TD target Rt+1 + γ maxa Q̂(St+1,a), the learning rate α, exploration, on/off-policy — all the Stage 2 ideas carry over. That's why Deep RL is "RL + deep nets," not a new field.
4What is the deadly triad, and why does it matter for Deep RL?›
It's the combination of function approximation + bootstrapping + off-policy learning. Each is useful alone, but together they can make value estimates diverge instead of converge. Deep Q-learning has all three, which is why DQN (3.2) adds tricks like experience replay and a target network to keep training stable.