Advanced Tabular Methods

Why Does This Exist?

Textbooks introduce dynamic programming, Monte Carlo methods and temporal-difference learning as three separate tribes. That split is handy for teaching. It misleads when you have to pick an update.

The extremes both hurt. One-step TD bootstraps after a single transition, so it learns online with low variance. But it leans hard on its own guesses, and a bad initial table poisons early updates while distant rewards crawl backward one state per episode. Monte Carlo waits for the full return, so it uses real outcomes with zero bootstrapping bias. But it stacks the noise of every step into one target, needs far more episodes, and cannot update at all inside a continuing task.

This page covers the bridge: n-step returns and the lambda mixture that turn that either-or choice into a dial. You will see the two axes the field uses (depth and width), the one formula that recovers both extremes, and a four-step chain worked by hand. The deep treatments of each endpoint live on their own pages. Start with tabular solution methods if the table setup itself is new.

Think of It Like This

How It Actually Works

Symbols for this page: $S_t$ is the state at time $t$, $R_{t+1}$ the reward after leaving it, $\gamma$ the discount factor in $[0, 1]$, $V(s)$ the table estimate, $n$ the backup depth, and $\lambda$ the mixture weight in $[0, 1]$. Depth counts how many real rewards enter the target before bootstrapping. Width counts whether the backup follows one sampled transition or averages over a full model.

Sample backups follow the single transition the environment dealt you. Full-width backups average over every outcome a model says is possible. Dynamic programming sits at depth 1 with full width. One-step TD sits at depth 1 with width 1. Monte Carlo sits at full depth with width 1. Everything else fills the space between.

The n-step return

Accumulate $n$ real rewards, then bootstrap from the table:

When the horizon runs past termination there is nothing left to bootstrap from, so the tail term drops and the return becomes the plain Monte Carlo return $G_t$. The update waits $n$ steps, then moves the table toward the target with step size $\alpha$:

Set $n = 1$ and you get the TD target $R_{t+1} + \gamma V(S_{t+1})$. Stretch $n$ past the episode end and you get Monte Carlo. Depth is a slider, not a school of thought.

The lambda mixture

Instead of picking one $n$, blend every horizon with geometric weights. With $\lambda$ in $[0, 1]$:

The weights sum to one by construction. At $\lambda = 0$ all weight lands on the one-step return. At $\lambda = 1$ all weight lands on Monte Carlo. In between you get a compound target that trusts real rewards for a few steps and cuts off the noisy tail with a bootstrap. Eligibility traces compute this same blend online, one step at a time, and n-step TD prediction treats the fixed-depth case in full.

Worked example with four rewards

A short chain ends after four rewards. Discount $\gamma = 0.9$, step size $\alpha = 0.2$:

Table values are $V(S_0) = 0.0$, $V(S_1) = 3.0$, $V(S_2) = 5.0$, $V(S_3) = 8.0$, terminal $0.0$. Targets for $S_0$:

One step uses one reward plus the table:

Two steps use two rewards plus the table at $S_2$:

Three steps reach $S_3$:

Four steps run past termination, so no bootstrap remains:

That last number is the Monte Carlo return $G_0$. Now mix with $\lambda = 0.5$. Weights are $0.500$, $0.250$, $0.125$ and $0.125$, which sum to $1.000$:

With $\alpha = 0.2$ from $V(S_0) = 0.0$, TD moves to $0.94$, two-step to $1.39$, three-step to $2.39$, the mixture moves to $1.45$, and Monte Carlo moves to $2.69$. TD under-reacts because the table entry $3.0$ is pessimistic. Monte Carlo grabs the $+10.0$ directly but would swing wildly if that last reward were noisy. The mixture sits between them, which is the whole point of the dial.

Code

A short check of the four targets and the lambda blend, with type hints throughout:

1from typing import List2
3
4def n_step_return(rewards: List[float], values: List[float], gamma: float, start: int, n: int) -> float:5    horizon = len(rewards)6    end = min(start + n, horizon)7    total = 0.08    for k in range(start, end):9        total += (gamma ** (k - start)) * rewards[k]10    if start + n < horizon:11        total += (gamma ** n) * values[start + n]12    return total13
14
15rewards = [2.0, 1.0, 4.0, 10.0]16values = [0.0, 3.0, 5.0, 8.0, 0.0]17gamma = 0.918alpha = 0.219
20targets = [n_step_return(rewards, values, gamma, 0, n) for n in [1, 2, 3, 4]]21print([round(t, 2) for t in targets])22# -> [4.7, 6.95, 11.97, 13.43]23
24weights = [0.5, 0.25, 0.125, 0.125]25mixed = sum(w * t for w, t in zip(weights, targets))26print(round(mixed, 2))27# -> 7.2628
29print([round(alpha * t, 2) for t in [targets[0], mixed, targets[3]]])30# -> [0.94, 1.45, 2.69]

1# -> expected output:2[4.7, 6.95, 11.97, 13.43]37.264[0.94, 1.45, 2.69]

Watch Out For

The Quick Version

• Tabular methods live on two axes: backup depth (how many rewards before bootstrapping) and backup width (one sampled transition or a full model average).
• The n-step return $G_{t:t+n}$ recovers TD at $n = 1$ and Monte Carlo when $n$ covers the episode.
• The lambda mixture blends every horizon with weights that sum to one, with $\lambda = 0$ giving TD and $\lambda = 1$ giving Monte Carlo.
• On rewards $[2.0, 1.0, 4.0, 10.0]$ with $\gamma = 0.9$, targets run $4.70$, $6.95$, $11.97$, $13.43$, and $\lambda = 0.5$ lands at $7.26$.
• Deeper backups cut bootstrapping bias but add sampling variance, so tune $n$ and $\lambda$ instead of switching families.

What to Read Next

• Tabular Solution Methods
• n-Step TD Prediction in RL
• Eligibility Traces