Tabular Solution Methods

Tabular methods store every value in its own table cell, so updating one state-action pair touches nothing else and the classic convergence proofs apply exactly.

A Q-learning step writes 3.75 into the single cell for state S2 and action right while the other seven cells of the 4 by 2 table stay exactly as they were

Why Does This Exist?

With a neural approximator, one update moves shared weights, so learning about state $s$ silently rewrites the values of states the agent never visited. That interference is one leg of the deadly triad and the reason deep value methods can diverge.

Tables have no shared weights. The value of $(s, a)$ lives in its own memory cell, and writing to it changes nothing else, bit for bit. That isolation is why every classical guarantee, from dynamic programming to Q-learning convergence, is proved in the tabular setting first. This page covers the table representation, the cell-local update, and the exact point where tables stop being viable. The model of the world those cells describe is built in MDP foundations.

Think of It Like This

A scoreboard with one bulb per play

Picture a stadium scoreboard wired so strangely that every possible play in every possible game situation has its own little bulb with a number painted on it. The bulb for third down at midfield shows 4.2 expected points. When that exact situation happens and the team scores, an electrician climbs up and repaints only that one bulb to 4.6. Every other bulb keeps its old paint.

That is a Q-table: cell $(s, a)$ holds the expected return, and an update repaints one bulb. A neural network is the opposite kind of scoreboard, where all bulbs share one dimmer switch and touching the switch brightens the whole board at once.

Where it stops: real scoreboards have dozens of bulbs. A robot arm with 8 joints at 20 positions each needs $20^8$ , about 25.6 billion bulbs, and most would never light up once. Nobody builds that scoreboard.

How It Actually Works

The state values form an array $V$ with one entry per state, and the action values form a matrix $Q$ with one entry per state-action pair. Learning is direct assignment, not gradient descent. From a transition $(s_t, a_t, R_{t+1}, s_{t+1})$ the agent forms the TD error

\delta_t = R_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a') - Q(s_t, a_t)

where $\gamma$ in $[0, 1)$ discounts the future, and writes back into the same cell:

Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha\,\delta_t

with step size $\alpha$ in $(0, 1]$ . No other cell is read for the write, and no other cell changes.

Why convergence is guaranteed here

The Bellman optimality backup is a contraction in the max norm: two tables get strictly closer, by at least a factor $\gamma$ , with each full sweep. Repeated sweeps therefore converge to one unique $Q^*$ . Sample-based Q-learning inherits this provided every pair is visited infinitely often and step sizes satisfy the Robbins-Monro decay conditions. All of this holds because a cell write cannot disturb its neighbors, which is precisely what approximators give up.

Worked example

Four states $S_0$ through $S_3$ with $S_3$ terminal, two actions left and right, $\alpha = 0.5$ , $\gamma = 0.9$ . Current table: $S_0$ holds $0.00$ and $1.25$ ; $S_1$ holds $0.50$ and $2.80$ ; $S_2$ holds $1.10$ and $3.50$ ; $S_3$ holds $0.00$ and $0.00$ .

The agent stands in $S_2$ , takes right, lands in terminal $S_3$ , reward $R = 4.00$ .

Look up the cell: $Q(S_2, \text{right}) = 3.50$ . Next-state value is $\max Q(S_3, \cdot) = 0.00$ since the episode ended. Target: $4.00 + 0.9 \times 0.00 = 4.00$ . Error: $\delta = 4.00 - 3.50 = 0.50$ . Write: $Q(S_2, \text{right}) \leftarrow 3.50 + 0.5 \times 0.50 = 3.75$ .

The neighboring entry $Q(S_2, \text{left}) = 1.10$ is untouched, as are all six remaining cells.

Code

1class QTable:2    """Explicit state-action table with cell-local Q-learning updates."""3
4    def __init__(self, rows: list[list[float]]) -> None:5        self.table = [row[:] for row in rows]6
7    def update(self, s: int, a: int, r: float, next_s: int,8               done: bool, alpha: float, gamma: float) -> tuple[float, float]:9        """One tabular Q-learning write; returns (td_error, new_value)."""10        next_max = 0.0 if done else max(self.table[next_s])11        td_error = (r + gamma * next_max) - self.table[s][a]12        self.table[s][a] += alpha * td_error13        return td_error, self.table[s][a]14
15
16q = QTable([[0.00, 1.25], [0.50, 2.80], [1.10, 3.50], [0.00, 0.00]])17err, new = q.update(2, 1, 4.0, 3, True, 0.5, 0.9)18print(f"{err:.2f}")  # -> 0.5019print(f"{new:.2f}")  # -> 3.7520print(f"{q.table[2][0]:.2f}")  # -> 1.1021print(f"{q.table[0][1]:.2f}")  # -> 1.25

Watch Out For

Discretizing a continuous task finely enough to need billions of cells

The failure mode is silent at first: training looks fine on a coarse grid, so you refine the bins to get smoother control, and suddenly nothing learns. Each visit now lands in a fresh cell, every estimate stays near its initialization, and the agent acts almost randomly for millions of steps. Memory follows the same explosion: 8 dimensions at 20 bins need tens of billions of floats.

The symptom that names the cause is coverage: count distinct visited cells per thousand steps. If it grows linearly without repeating, the table is too big to ever fill. The fix is to stop tabulating and switch to function approximation, such as tile coding for a gentle start or deep Q-networks when the space is truly large.

Starving cells with an epsilon that decays too fast

Q-learning converges only if every pair keeps being visited. If exploration decays to zero early, rarely visited cells freeze at bad values and the greedy policy routes around them forever, so they never get corrected. The symptom is a policy that is confidently wrong in whole regions: evaluation returns plateau while the supposedly optimal actions in those regions still hold their initial values.

The fix is to keep a floor under exploration, such as epsilon never below $0.05$ , or to use optimistic initialization so unvisited cells look attractive until tried. Check the visit counts directly before blaming the update rule.

The Quick Version

Tabular methods store one number per state or state-action pair, with no shared parameters.
A Q-learning update reads one cell, computes one TD error, and writes one cell back.
Cell-local writes mean zero interference, which is what makes the classical contraction proofs work.
The worked step lifts Q(S2, right) from 3.50 to 3.75 and changes nothing else in the 4 by 2 table.
The price is the curse of dimensionality: fine grids over continuous spaces need billions of cells.
Every pair must keep being visited, or unvisited cells freeze at bad values behind a greedy policy.