Advanced Robotics / Reinforcement Learning · Lesson 06
Why Tabular Q Breaks
Est. 60–75 min
Why
Why this lesson matters
In Lessons 2–5 every learner kept a Q-table: one number for every (state, action) pair. That is perfect for 9 angle bins or a 15-cell lab floor. But a table needs a separate box for every combination of state variables, so its size grows by multiplication, not addition. Richard Bellman called this the curse of dimensionality — the amount of data you need grows exponentially with the number of dimensions.
Today you will measure the explosion three ways: count table sizes for real robots, train the same learner on bigger and bigger grids with the same practice budget, and try to hold a continuous servo angle with coarse and fine bins. On the bench, the UNO itself will tell you which tables fit in its 2 KB of RAM. By the end you will know exactly *why* robots need function approximation — the subject of Lesson 7.
Concept
Tables, dimensions and the curse
1. A table has one box per combination
If a robot state is described by *d* variables and each one is cut into *n* bins, the number of states is n^d. Multiply by the number of actions and you get the number of Q-values to store and to learn. Every one of them must be visited many times before it is trustworthy, because tabular Q-learning learns each box separately — what it learns at 40° tells it nothing about 45°.
| Robot | State description | Q-values | Memory (float32) |
|---|---|---|---|
| Light-seeker (L04) | 9 angle bins × 3 actions | 27 | 108 B |
| Lab floor (L03) | 15 cells × 4 actions | 60 | 240 B |
| 2-joint arm | 10² states × 3² actions | 900 | 3.5 KB |
| 6-joint arm | 10⁶ states × 3⁶ actions | 729,000,000 | 2.7 GB |
| 6-joint arm + speeds | 10¹² states × 3⁶ actions | 7.29 × 10¹⁴ | about 2,652 TB |
| 64 × 64 grey camera | 256⁴⁰⁹⁶ states | a number with 9,865 digits | impossible |

2. Memory is the small problem; experience is the big one
Even if you had unlimited memory, the robot still has to visit every box enough times. A 6-joint table with 729 million entries would need billions of real arm movements — years of motor wear — before every value is learnt. In our grid test below, the learner did 38–65 updates per Q-value on average and still failed on the bigger grids: the updates pile up near the start, and the good news from the goal travels back only one cell per update.

3. Continuous states: the bin trade-off
Real sensors are continuous: an angle can be 47.3°, not just “bin 4”. To use a table we discretise (cut into bins). Coarse bins learn fast but cannot be precise — the robot cannot tell 80° from 100°. Fine bins could be precise but each bin is visited rarely, so most of the table stays at its starting value. There is no bin width that is good at both.
Visual
Visualise it: from a table to a network
A preview of where we are heading: instead of one box per state, a small network maps a state to Q-values for every action. Collect, train, sync — and watch the estimates change for states you never visited. (Educational simulation.)
Interactive · DQN intuition lab · Educational value-based deep RL toy
Table cells
16
Q(s,a) entries
Net params
4
linear φ · 2 feats × 2 acts
|TD| mean
0.000
last train batch
Lane · arrows = greedy from online Q · start left · G = goal · α=0.25 γ=0.9 · steps=0
Online Q-net (updating)
← [0.00, 0.00] → [0.00, 0.00]
Target Q-net (lagged) · sync in 8
← [0.00, 0.00] → [0.00, 0.00]
Replay buffer (0/24) · highlight = last sampled batch
|TD error| sparkline
Collect with ε-greedy → store in replay → sample batch → update online Q → sync target.
φ(s)=[pos_norm, dist_to_goal] · Q(s,a)=w_a·φ · target bootstraps TD · replay breaks step correlation — intuition only.
Code lab
Code lab: watch the table explode
table_explosion_lab.py has three parts. Part 1 counts Q-table sizes. Part 2 runs the same tabular Q-learner (α 0.3, γ 0.95, ε 1 → 0.05, −1 per step, +10 at the goal) for 300 episodes on empty grids from 5×5 to 80×80, then tests the greedy policy. Part 3 trains a servo to move to 90° and hold it, with the angle cut into 3 to 900 bins (actions −5°, 0, +5°; 300 episodes; 5 seeds). Standard library only.
"""table_explosion_lab.py - Stage 14 L06: why tabular Q-learning breaks.
Part 1: count Q-table sizes for real robot state descriptions.
Part 2: same learner, same budget, bigger worlds - how much of the table is ever visited?
Part 3: continuous state - discretise a 0..180 deg servo angle; coarse bins lose
accuracy, fine bins learn too slowly. Neither is good. (The fix: Lesson 7.)
Standard library only.
"""
import random
print("1) How big is the table? (4 bytes per float32 Q-value)")
cases = [
("light-seeker: 9 angle bins x 3 actions", 9, 3),
("L03 lab floor: 15 cells x 4 actions", 15, 4),
("2-joint arm, 10 bins/joint, 3 actions/joint", 10 ** 2, 3 ** 2),
("6-joint arm, 10 bins/joint, 3 actions/joint", 10 ** 6, 3 ** 6),
("6-joint arm + joint speeds, 10 bins each", 10 ** 12, 3 ** 6),
("64x64 grey camera image (256 levels/pixel)", None, 4),
]
for name, ns, na in cases:
if ns is None:
print(f" {name:46s} states = 256^4096 (a number with 9865 digits) -> impossible")
continue
entries = ns * na
b = entries * 4
size = (f"{b} B" if b < 1024 else f"{b / 1024:.1f} KB" if b < 1024 ** 2 else
f"{b / 1024 ** 2:.1f} MB" if b < 1024 ** 3 else f"{b / 1024 ** 3:.1f} GB" if b < 1024 ** 4
else f"{b / 1024 ** 4:,.0f} TB")
print(f" {name:46s} entries {entries:>18,d} memory {size}")
def grid_q(size, episodes, seed):
"""Q-learning on an empty size x size grid, start (0,0), goal opposite corner, -1/step."""
rng = random.Random(seed)
Q, updates = {}, 0
moves = [(-1, 0), (0, 1), (1, 0), (0, -1)]
goal = (size - 1, size - 1)
for ep in range(episodes):
s, eps = (0, 0), max(0.05, 1 - ep / (episodes * 0.6))
for _ in range(4 * size * size):
q = Q.setdefault(s, [0.0] * 4)
a = rng.randrange(4) if rng.random() < eps else max(range(4), key=lambda i: (q[i], rng.random()))
r, c = s[0] + moves[a][0], s[1] + moves[a][1]
s2 = (min(max(r, 0), size - 1), min(max(c, 0), size - 1))
done = s2 == goal
target = 10.0 if done else -1.0 + 0.95 * max(Q.setdefault(s2, [0.0] * 4))
q[a] += 0.3 * (target - q[a])
updates += 1
s = s2
if done:
break
# greedy test
s, steps = (0, 0), 0
while s != goal and steps < 4 * size * size:
q = Q.get(s, [0.0] * 4)
a = max(range(4), key=lambda i: q[i])
r, c = s[0] + moves[a][0], s[1] + moves[a][1]
s = (min(max(r, 0), size - 1), min(max(c, 0), size - 1))
steps += 1
return updates / (size * size * 4), s == goal, steps, 2 * (size - 1)
print("\n2) Same learner, same budget (300 episodes), bigger grids (5 seeds)")
print(f" {'grid':>7s} {'states':>7s} {'updates per Q entry':>20s} {'greedy reaches goal':>20s} {'steps (best possible)':>22s}")
for size in (5, 10, 20, 40, 80):
vis, ok, st = 0.0, 0, []
for seed in range(5):
v, reached, steps, best = grid_q(size, 300, seed)
vis += v / 5
ok += reached
if reached:
st.append(steps)
s_txt = f"{sum(st) / len(st):.0f}" if st else "-"
print(f" {size:3d}x{size:<3d} {size * size:7d} {vis:16.1f} {ok:>14d}/5 {s_txt:>14s} ({best})")
def servo_task(bins, episodes, seed):
"""Point a servo at a hidden target angle (0..180) and HOLD it there.
State = binned current angle. Actions: -5, 0, +5 deg. Reward -|error|/10 every step.
40 steps per episode, no early stop: what counts is where it ends up and stays."""
rng = random.Random(seed)
Q = {}
width = 180 / bins
def b(x):
return min(bins - 1, int(x / width))
target = 90.0
for ep in range(episodes):
x, eps = rng.uniform(0, 180), max(0.05, 1 - ep / (episodes * 0.6))
for _ in range(40):
s = b(x)
q = Q.setdefault(s, [0.0] * 3)
a = rng.randrange(3) if rng.random() < eps else max(range(3), key=lambda i: (q[i], rng.random()))
x = min(180.0, max(0.0, x + (a - 1) * 5))
r = -abs(x - target) / 10
q[a] += 0.3 * (r + 0.9 * max(Q.setdefault(b(x), [0.0] * 3)) - q[a])
errs = []
for t in range(50):
x = rng.uniform(0, 180)
for _ in range(40):
q = Q.get(b(x), [0.0] * 3)
x = min(180.0, max(0.0, x + (max(range(3), key=lambda i: q[i]) - 1) * 5))
errs.append(abs(x - target))
return sum(1 for e in errs if e <= 5) / 50, sum(errs) / len(errs)
print("\n3) Continuous angle: hold 90 deg. How many bins? (300 training episodes, 5 seeds)")
print(f" {'bins':>5s} {'bin width':>10s} {'ends within 5 deg':>18s} {'avg final error':>16s}")
for bins in (3, 9, 36, 180, 900):
hit, err = 0.0, 0.0
for seed in range(5):
h, e = servo_task(bins, 300, seed)
hit += h / 5
err += e / 5
print(f" {bins:5d} {180 / bins:8.1f} deg {hit * 100:15.0f} % {err:13.1f} deg")Output (run with python3 table_explosion_lab.py)
1) How big is the table? (4 bytes per float32 Q-value)
light-seeker: 9 angle bins x 3 actions entries 27 memory 108 B
L03 lab floor: 15 cells x 4 actions entries 60 memory 240 B
2-joint arm, 10 bins/joint, 3 actions/joint entries 900 memory 3.5 KB
6-joint arm, 10 bins/joint, 3 actions/joint entries 729,000,000 memory 2.7 GB
6-joint arm + joint speeds, 10 bins each entries 729,000,000,000,000 memory 2,652 TB
64x64 grey camera image (256 levels/pixel) states = 256^4096 (a number with 9865 digits) -> impossible
2) Same learner, same budget (300 episodes), bigger grids (5 seeds)
grid states updates per Q entry greedy reaches goal steps (best possible)
5x5 25 51.0 5/5 8 (8)
10x10 100 38.6 5/5 18 (18)
20x20 400 45.2 0/5 - (38)
40x40 1600 56.2 0/5 - (78)
80x80 6400 65.2 0/5 - (158)
3) Continuous angle: hold 90 deg. How many bins? (300 training episodes, 5 seeds)
bins bin width ends within 5 deg avg final error
3 60.0 deg 1 % 28.7 deg
9 20.0 deg 3 % 8.3 deg
36 5.0 deg 89 % 11.3 deg
180 1.0 deg 37 % 37.8 deg
900 0.2 deg 11 % 45.1 degTry it: a tiny Q-network instead of a table. Collect transitions, train on mini-batches and sync the target network — you will meet each of these ideas properly in Lessons 7–9. (Educational simulation.)
Interactive · DQN intuition lab · Educational value-based deep RL toy
Table cells
16
Q(s,a) entries
Net params
4
linear φ · 2 feats × 2 acts
|TD| mean
0.000
last train batch
Lane · arrows = greedy from online Q · start left · G = goal · α=0.25 γ=0.9 · steps=0
Online Q-net (updating)
← [0.00, 0.00] → [0.00, 0.00]
Target Q-net (lagged) · sync in 8
← [0.00, 0.00] → [0.00, 0.00]
Replay buffer (0/24) · highlight = last sampled batch
|TD error| sparkline
Collect with ε-greedy → store in replay → sample batch → update online Q → sync target.
φ(s)=[pos_norm, dist_to_goal] · Q(s,a)=w_a·φ · target bootstraps TD · replay breaks step correlation — intuition only.
Bench build: how big a table fits in an UNO?
table_budget.ino really allocates the 36-bin light-seeker table (36 × 3 floats = 432 bytes), measures the free RAM left, then checks seven designs: does each table fit as float32 (4 bytes per value), only as int8 (1 byte, less precision), or not at all?
| Part | Connection | Note |
|---|---|---|
| Arduino UNO R3 | USB to the laptop | no other wiring for this sketch |
| (Optional) light-seeker servo + LDR from L04 | leave it unplugged or unpowered | this test only prints numbers |
// table_budget.ino - Stage 14 L06
// How big a Q-table can an Arduino UNO hold? Measure free RAM, then test real table sizes.
// The UNO's ATmega328P has 2048 bytes of SRAM (the compiler report says so) and 1 KB EEPROM.
// No wiring needed - just USB. Serial 115200.
//
// For each design it prints: states, actions, bytes needed (float = 4 B, int8 = 1 B) and
// whether it fits in the free RAM measured right now.
struct Design { const char *name; unsigned long states; unsigned long actions; };
extern int __heap_start, *__brkval;
int freeRam() { // classic AVR trick: gap between heap and stack
int v;
return (int)&v - (__brkval == 0 ? (int)&__heap_start : (int)__brkval);
}
const Design designs[] = {
{"light-seeker 9 bins", 9UL, 3UL},
{"light-seeker 36 bins", 36UL, 3UL},
{"L03 lab floor 4x4", 16UL, 4UL},
{"20x20 grid", 400UL, 4UL},
{"2 joints x 10 bins, 9 actions", 100UL, 9UL},
{"3 joints x 10 bins, 27 actions", 1000UL, 27UL},
{"6 joints x 10 bins, 729 actions", 1000000UL, 729UL},
};
void printRow(const Design &d, int freeBytes) {
unsigned long long entries = (unsigned long long)d.states * d.actions;
unsigned long long asFloat = entries * 4ULL, asInt8 = entries;
Serial.print(d.name); Serial.print(F(" | entries "));
if (entries > 4000000000ULL) Serial.print(F(">4e9")); else Serial.print((unsigned long)entries);
Serial.print(F(" | float32 "));
if (asFloat > 4000000000ULL) Serial.print(F(">4e9")); else Serial.print((unsigned long)asFloat);
Serial.print(F(" B | int8 "));
if (asInt8 > 4000000000ULL) Serial.print(F(">4e9")); else Serial.print((unsigned long)asInt8);
Serial.print(F(" B | "));
if (asFloat <= (unsigned long long)freeBytes) Serial.println(F("fits as float"));
else if (asInt8 <= (unsigned long long)freeBytes) Serial.println(F("fits only as int8 (less precision)"));
else if (asInt8 <= 1024ULL) Serial.println(F("too big for RAM; int8 would fit the 1 KB EEPROM"));
else Serial.println(F("DOES NOT FIT"));
}
volatile float smallTable[36][3]; // the 36-bin light-seeker table, really allocated (volatile keeps it in RAM)
void setup() {
Serial.begin(115200);
delay(500);
for (int s = 0; s < 36; s++) for (int a = 0; a < 3; a++) smallTable[s][a] = 0;
int freeBytes = freeRam();
Serial.print(F("# free RAM right now: ")); Serial.print(freeBytes); Serial.println(F(" bytes"));
Serial.println(F("# (smallTable[36][3] already uses 432 bytes of the 2048)"));
for (unsigned int i = 0; i < sizeof(designs) / sizeof(designs[0]); i++) printRow(designs[i], freeBytes);
Serial.println(F("# Lesson: tables grow as bins^joints. Even a 3-joint arm does not fit."));
}
void loop() {}# free RAM right now: <about a thousand> bytes
# (smallTable[36][3] already uses 432 bytes of the 2048)
light-seeker 9 bins | entries 27 | float32 108 B | int8 27 B | fits as float
...
2 joints x 10 bins, 9 actions | entries 900 | float32 3600 B | int8 900 B | <fits only as int8?>
3 joints x 10 bins, 27 actions | entries 27000 | ... | DOES NOT FIT
6 joints x 10 bins, 729 actions | entries 729000000 | ... | DOES NOT FIT
# Lesson: tables grow as bins^joints. Even a 3-joint arm does not fit.Debugging
| Symptom | Likely cause | Fix |
|---|---|---|
| Sketch uploads but behaves randomly or resets | table plus stack larger than free RAM | Check free RAM; shrink the table or use int8 |
| “does not name a type” compile error | Arduino auto-prototypes placed above your struct | Put struct definitions at the very top of the sketch |
| RAM report smaller than your table | the optimiser removed an unused array | Read the array somewhere, or mark it volatile for tests |
| Python uses all memory and freezes | building a full n^d table | Use a dict that only stores visited states — or a function approximator |
| Big grid never learns | too few visits per useful state | More episodes helps a bit; the real fix is generalisation (Lesson 7) |
| Finer bins make results worse | each bin visited too rarely | Pick a medium bin size or move to function approximation |
Real world
Where tables stop working in the real world

- Robot arms: joint angles and speeds are continuous, and an arm has 6 or more of them. Tables are hopeless; learning methods use functions with weights instead.
- Camera-based control: a single small grey image already has more possible states than any table could list. Learning from pixels needs a function that generalises — a neural network (Lesson 8).
- Embedded boards: the UNO’s ATmega328P has 2 KB RAM. A laptop with gigabytes strains at six joints and gives up completely once speeds are added.
- Bellman’s curse: the same problem appears in dynamic programming, statistics and machine learning — whenever you try to cover a space by listing every cell.

Think
Think about it
Think
Your 2-joint arm uses 10 bins per joint. You add a gripper that can be open, half-open or closed. How many states now? How many Q-values with 3 actions per joint and 3 gripper actions?
Experiment
Try it in the lab
About 60 minutes. Python 3 for the table tests; an Arduino UNO on USB for the memory test.
Experiment
Find the breaking point
You will need
- `table_explosion_lab.py` (Python 3, no libraries)
- DQN intuition lab (in your browser)
- Arduino UNO R3 and USB cable
- Notebook for the results tables
Steps
- Run `table_explosion_lab.py`. Copy all three tables into your notebook.
- In Part 2, change 300 episodes to 3000. Which grid sizes are solved now? How long did it take to run?
- In Part 3, try 18 and 72 bins. Draw a graph: bins on the x-axis (log scale), “within 5°” on the y-axis.
- Add your own row to Part 1 for the lab arm you use (count joints, pick bins per joint).
- Upload `table_budget.ino`. Write down the free RAM. Change smallTable to 72 bins and upload again — how much free RAM is left?
- In the DQN intuition lab, collect transitions and train a few batches. Notice that one small set of weights gives Q-values for every state.
Interactive · DQN intuition lab · Educational value-based deep RL toy
Table cells
16
Q(s,a) entries
Net params
4
linear φ · 2 feats × 2 acts
|TD| mean
0.000
last train batch
Lane · arrows = greedy from online Q · start left · G = goal · α=0.25 γ=0.9 · steps=0
Online Q-net (updating)
← [0.00, 0.00] → [0.00, 0.00]
Target Q-net (lagged) · sync in 8
← [0.00, 0.00] → [0.00, 0.00]
Replay buffer (0/24) · highlight = last sampled batch
|TD error| sparkline
Collect with ε-greedy → store in replay → sample batch → update online Q → sync target.
φ(s)=[pos_norm, dist_to_goal] · Q(s,a)=w_a·φ · target bootstraps TD · replay breaks step correlation — intuition only.
Tables are exact and simple, but their size grows as bins^variables and each box must be learnt separately. More episodes push the breaking point a little further; they do not remove it. Fine bins need even more experience. What we need is a model that generalises between nearby states.
Knowledge check
Check your understanding
Knowledge check
1. A robot has 4 state variables with 10 bins each. How many states?
2. The “curse of dimensionality” was named by…
3. Why does tabular Q-learning learn slowly in big state spaces?
4. In Part 2, the 40×40 grid had 56 updates per Q-value but failed. Why?
5. In Part 3, why did 900 bins do worse than 36 bins?
6. How much SRAM does the ATmega328P on an UNO have?
7. What is the main idea that fixes the table explosion?
8. Adding one joint (10 bins, 3 actions) to an arm table multiplies its size by…
Mini assignment
Hands-on assignment
Mini assignment
State-space budget for your lab robot
Show, with numbers, where a table stops working for a robot in your lab.
Deliverables
- A state-space table for one real robot in your lab: list every state variable, its range and a sensible bin size, then compute states, actions, Q-values and memory.
- Your Part 2 results at 300 and 3000 episodes, with a one-line conclusion.
- Your Part 3 graph (bins vs “within 5°”) including the 18- and 72-bin runs.
- The UNO free-RAM reading before and after changing smallTable, and the largest light-seeker table you think could fit.
Do this, step by step
- List every state variable of one lab robot with range and bin size; compute states, Q-values and memory.
- Run
table_explosion_lab.pyPart 2 at 300 and 3000 episodes. - Run Part 3 with 18 and 72 bins too and draw bins vs “within 5°”.
- Bench: upload
table_budget.inoand note the free RAM. - Change smallTable to 72 bins, upload again and note the new free RAM.
Stuck? Hints, one at a time
- Memory = states × actions × bytes per value (4 for float32, 1 for int8).
- More bins need more episodes: each bin must be visited many times before its values mean anything.
- The UNO has only 2048 bytes of RAM in total — leave a few hundred free for the stack and Serial.
Challenges (pick by level)
- 🟢 Beginner: A traffic light has 3 colours. How many combined states do 2, 4 and 8 independent traffic lights have? Plot them.
- 🟡 Intermediate: Change Part 2 to store only visited states (it already uses a dict). Print how many states were ever visited on each grid as a percentage of all states.
- 🟠 Advanced: Replace the bins in Part 3 with tile coding (two or three overlapping bin grids, shifted by half a bin) and compare accuracy.
- 🔴 Expert: Store the light-seeker Q-table as int8 with a scale factor in EEPROM, so learning survives a power cut. Measure the precision you lose.
- ⚫ Research: Read the Curse of dimensionality article on Wikipedia and explain, with one example, why “nearby” points become rare in high dimensions.
Next step
A table stores one number per box. In Lesson 7 — Function Approximation Intuition you will replace it with a formula: a few weights that give a Q-value for *any* state, so that learning at 40° also improves 41°. That one change is what makes learning on real arms possible.
Look back: Lesson 5: Reward Shaping for Manipulation. Next: Lesson 7: Function Approximation Intuition. Related: Stage 12 — Simulation & Digital Twin.
Sources
- Wikipedia — Curse of dimensionality — term coined by Richard E. Bellman in dynamic programming; data needed grows exponentially with dimension.
- Wikipedia — Q-learning — the tabular update used in the code; Q-values stored per (state, action).
- [Sutton & Barto — Reinforcement Learning: An Introduction (2nd ed., free online)](http://incompleteideas.net/book/the-book-2nd.html) — Part I “Tabular Solution Methods” (Ch. 2–8) versus Part II “Approximate Solution Methods” (Ch. 9–13).
- Arduino Docs — UNO R3 — ATmega328P, 1 KB EEPROM, 14 digital and 6 analog pins. RAM (2048 B) and flash (32256 B usable) figures are from the arduino-cli compile report.
- Photos: Wikimedia Commons (credits under each image).
Self-attested for now — keep artifacts in your lab notebook.
Complete
Today's goal
0 of 1 done today
Mark this lesson complete when you have worked the experiment, knowledge check, and assignment (even roughly).