Advanced Tabular Methods

Why Does This Exist?

Introductory reinforcement learning texts often introduce Dynamic Programming, Monte Carlo Methods, and Temporal Difference Learning as three rival, disconnected paradigms. Practitioners are taught to make a binary decision: either assume a known transition model and run dynamic programming sweeps, or sample trial-and-error experience model-free using TD or Monte Carlo.

This siloed perspective breaks down in practice because extreme algorithmic choices carry severe theoretical and practical penalties:

1. Pure One-Step TD (TD(0)) bootstraps immediately after a single transition. It updates value estimates online without waiting for an episode to terminate, yielding low sample variance. However, when value tables are initialized arbitrarily or poorly approximated, bootstrapping compounds estimation bias, causing credit assignment for distant terminal rewards to propagate backward agonizingly slowly—one state per episode.
2. Pure Monte Carlo waits until an episode terminates to tally the complete empirical return. Because it uses actual observed outcomes rather than value estimates, it is completely unbiased with respect to future bootstrapping errors. Yet its variance is extreme: every random action and stochastic environment transition along an extended trajectory compounds exponentially, demanding vast quantities of data to converge. Furthermore, Monte Carlo cannot learn during an ongoing task or in non-terminating, continuing environments.

Advanced tabular methods exist to unify these seemingly disparate algorithms into a single mathematical continuum. By introducing $n$-step returns and eligibility traces, Richard Sutton and Andrew Barto mapped all tabular learning onto a unified two-dimensional coordinate space defined by backup depth (how many time steps forward an agent looks before bootstrapping) and backup width (whether the update averages across all possible model transitions or follows a single sampled trajectory).

Unification transforms algorithmic selection from an either-or compromise into a continuous hyperparameter tuning problem, allowing agents to strike an optimal balance between bias and variance.

Think of It Like This

How It Actually Works

The Two-Dimensional Unified Space and the n-Step Continuum

Sutton & Barto organize all tabular reinforcement learning algorithms across two orthogonal dimensions:

1Backup Width (Degree of Distributional Expectation)2   ▲3   │  [Dynamic Programming]              [Exhaustive Search]4   │  Full distribution backup            Full distribution tree rollout5   │  Depth = 1 step, Width = Full        Depth = ∞, Width = Full6   │7   │  [Dyna / Model-Based Planning]       [Monte Carlo Tree Search]8   │  Intermediate width                  Branching sampled rollouts9   │10   │  [One-Step TD / TD(0)] ──► [n-Step TD & TD(λ)] ──► [Monte Carlo]11   │  Single sample backup       Bridging continuum       Single sample rollout12   │  Depth = 1 step, Width = 1  Depth = n, Width = 1     Depth = ∞, Width = 113   └─────────────────────────────────────────────────────────────► Backup Depth14      1-Step                      Intermediate n          Full Episode (∞)

1. Backup Depth (Horizontal Axis): Governs how far into the future the agent accumulates true sampled rewards before bootstrapping off the estimated value of the subsequent state.
2. Backup Width (Vertical Axis): Governs the branching factor of the backup. A sample backup (model-free) follows the single transition $(S_t, A_t, R_{t+1}, S_{t+1})$ actually sampled by the environment. A full distribution backup (model-based Dynamic Programming) uses transition probabilities $p(s', r | s, a)$ to compute the exhaustive mathematical expectation across all potential outcomes.

The n-Step Return Formulation

Let an agent generate a trajectory of states, actions, and rewards:

where:

• $S_t \in \mathcal{S}$ is the state visited at time $t$.
• $A_t \in \mathcal{A}$ is the action taken at time $t$.
• $R_{t+1} \in \mathbb{R}$ is the numerical reward received after transition.
• $\gamma \in [0, 1]$ is the discount factor for future rewards.
• $T$ is the terminal time step of the episode.
• $V_t(s)$ is the tabular value estimate of state $s$ available at time step $t$.

The generalized $n$-step return $G_{t:t+n}$ accumulates $n$ discounted rewards and bootstraps using the value estimate of the state reached at step $t+n$:

If $t + n \ge T$ (the horizon extends beyond episode termination), the bootstrapping term vanishes, and the $n$-step return truncates to the complete episodic return:

The tabular value update rule applied at time step $t+n$ (once the required $n$ steps of experience have been observed) is:

where $\alpha \in (0, 1]$ is the step-size learning rate parameter.

Notice how the boundaries recover classical algorithms exactly:

• When $n = 1$: $G_{t:t+1} = R_{t+1} + \gamma V_t(S_{t+1})$, recovering standard one-step TD(0).
• When $n = \infty$ (or $n \ge T - t$): $G_{t:T} = G_t = \sum_{k=0}^{T-t-1} \gamma^k R_{t+k+1}$, recovering full Monte Carlo.

The Compound $\lambda$-Return and Eligibility Traces Bridge

Rather than selecting a single fixed horizon $n$, advanced tabular methods can average multiple $n$-step returns. The $\lambda$-return $G_t^\lambda$ combines every possible $n$-step return into a single compound target using a geometric weighting parameterized by $\lambda \in [0, 1]$:

The weighting terms $(1-\lambda)\lambda^{n-1}$ form a geometric progression that sums to $1$:

• Setting $\lambda = 0$ places $100\%$ of the weight on $G_{t:t+1}$, recovering TD(0).
• Setting $\lambda = 1$ places all weight on the terminal Monte Carlo return $G_t$.
• Setting $\lambda \in (0, 1)$ smoothly interpolates across all horizons simultaneously.

While computing $G_t^\lambda$ directly (the forward view) requires looking ahead until the end of the episode, the backward view of Eligibility Traces uses short-term memory traces $e_t(s)$ to produce the exact same total weight updates online and incrementally at every time step with $O(1)$ complexity per transition:

Worked numerical example

Consider an agent navigating a 4-step trajectory that terminates at state $S_4$:

Let the discount factor be $\gamma = 0.9$ and the step-size learning rate be $\alpha = 0.2$.

The initial tabular state-value estimates are:

• $V(S_0) = 0.0$
• $V(S_1) = 3.0$
• $V(S_2) = 5.0$
• $V(S_3) = 8.0$
• $V(S_4) = 0.0$ (terminal state value is identically zero)

We compute the updated value $V(S_0)$ using different backup depths along the spectrum.

Step 1: Compute n-Step Returns for $n \in \{1, 2, 3, 4\}$

1. One-step return ($n = 1$, TD(0)):

   $$G_{0:1} = R_1 + \gamma V(S_1) = 2.0 + 0.9 \times 3.0 = 2.0 + 2.70 = 4.70$$

2. Two-step return ($n = 2$):

   $$G_{0:2} = R_1 + \gamma R_2 + \gamma^2 V(S_2) = 2.0 + 0.9(1.0) + (0.9)^2(5.0) = 2.0 + 0.90 + 4.05 = 6.95$$

3. Three-step return ($n = 3$):

   $$G_{0:3} = R_1 + \gamma R_2 + \gamma^2 R_3 + \gamma^3 V(S_3) = 2.0 + 0.9(1.0) + 0.81(4.0) + 0.729(8.0) = 2.0 + 0.90 + 3.24 + 5.832 = 11.972$$

4. Four-step return ($n = 4$, full Monte Carlo return $G_0$):

   $$G_{0:4} = R_1 + \gamma R_2 + \gamma^2 R_3 + \gamma^3 R_4 + \gamma^4 V(S_4) = 2.0 + 0.9(1.0) + 0.81(4.0) + 0.729(10.0) + 0 = 2.0 + 0.90 + 3.24 + 7.29 = 13.430$$

Step 2: Compute the Compound $\lambda$-Return for $\lambda = 0.5$

The episode length is $T = 4$. For $\lambda = 0.5$, we evaluate the geometric weights assigned to each $n$-step return:

• Weight for $n = 1$: $(1 - 0.5) \times (0.5)^0 = 0.500$
• Weight for $n = 2$: $(1 - 0.5) \times (0.5)^1 = 0.250$
• Weight for $n = 3$: $(1 - 0.5) \times (0.5)^2 = 0.125$
• Weight for $n = 4$ (terminal remainder): $(0.5)^3 = 0.125$

Check sum of weights:

The compound $\lambda$-return is:

Step 3: Compare Value Updates for $V(S_0)$

Applying the update rule $V(S_0) \leftarrow V(S_0) + \alpha [ \text{Target} - V(S_0) ]$ with $\alpha = 0.2$ and initial $V(S_0) = 0.0$:

• TD(0) ($n=1$): $V(S_0) \leftarrow 0.0 + 0.2(4.70 - 0.0) = 0.94$
• Compound $\lambda$-Return ($\lambda=0.5$): $V(S_0) \leftarrow 0.0 + 0.2(7.26 - 0.0) = 1.45$
• Monte Carlo ($n=4$): $V(S_0) \leftarrow 0.0 + 0.2(13.43 - 0.0) = 2.69$

Notice how the target scales monotonically from $4.70$ up to $13.43$. Pure TD(0) under-reacts because it relies heavily on the underestimated initial table entry $V(S_1) = 3.0$. Pure Monte Carlo captures the large $+10.0$ reward directly but is vulnerable to trajectory variance in stochastic domains. The intermediate $\lambda$-return strikes a balanced compromise at $7.26$.

Code

1from typing import Dict, List, Tuple2
3
4def compute_n_step_return(5    rewards: List[float],6    states: List[int],7    values: Dict[int, float],8    gamma: float,9    start_t: int,10    n: int,11) -> float:12    """Compute the n-step return G_{t:t+n} for starting step t.13    14    Args:15        rewards: Sequence of observed rewards [R_1, R_2, ..., R_T].16        states: Sequence of visited states [S_0, S_1, ..., S_T].17        values: Tabular dictionary mapping discrete state ids to value estimates.18        gamma: Discount factor in [0, 1].19        start_t: Origin time step t being evaluated.20        n: Number of backup steps (horizon window).21
22    Returns:23        The calculated n-step return G_{t:t+n}.24    """25    horizon = len(rewards)26    end_t = min(start_t + n, horizon)27
28    # Accumulate discounted rewards over the n-step window29    discounted_reward_sum = 0.030    for k in range(start_t, end_t):31        discounted_reward_sum += (gamma ** (k - start_t)) * rewards[k]32
33    # Bootstrap from estimated value of state reached at start_t + n34    target_idx = start_t + n35    if target_idx <= horizon:36        bootstrap_state = states[target_idx]37        bootstrap_val = (gamma ** n) * values.get(bootstrap_state, 0.0)38    else:39        bootstrap_val = 0.040
41    return discounted_reward_sum + bootstrap_val42
43
44def compute_lambda_return(45    rewards: List[float],46    states: List[int],47    values: Dict[int, float],48    gamma: float,49    start_t: int,50    lam: float,51) -> Tuple[float, List[Tuple[int, float, float]]]:52    """Compute the compound lambda-return as a geometric mixture of n-step returns.53
54    Args:55        rewards: Sequence of observed rewards [R_1, ..., R_T].56        states: Sequence of visited states [S_0, ..., S_T].57        values: Tabular state-value dictionary.58        gamma: Discount factor.59        start_t: Starting time step.60        lam: Lambda parameter in [0, 1].61
62    Returns:63        A tuple of (compound_return, list_of_tuples(n, return_n, weight_n)).64    """65    horizon = len(rewards)66    remaining_steps = horizon - start_t67    n_step_data: List[Tuple[int, float, float]] = []68    compound_return = 0.069
70    for n in range(1, remaining_steps + 1):71        g_n = compute_n_step_return(rewards, states, values, gamma, start_t, n)72        if n < remaining_steps:73            weight = (1.0 - lam) * (lam ** (n - 1))74        else:75            weight = lam ** (n - 1)  # Terminal remainder absorbs residual weight76        n_step_data.append((n, g_n, weight))77        compound_return += weight * g_n78
79    return compound_return, n_step_data80
81
82# Trajectory: S0 -> S1 -> S2 -> S3 -> S4 (terminal)83trajectory_states = [0, 1, 2, 3, 4]84trajectory_rewards = [2.0, 1.0, 4.0, 10.0]85state_values = {0: 0.0, 1: 3.0, 2: 5.0, 3: 8.0, 4: 0.0}86discount = 0.987alpha = 0.288
89print("=== N-Step Returns from State S0 ===")90for n in range(1, 5):91    ret = compute_n_step_return(92        trajectory_rewards, trajectory_states, state_values, discount, 0, n93    )94    label = "TD(0)" if n == 1 else ("Monte Carlo" if n == 4 else f"{n}-Step")95    print(f"n={n} ({label:11s}): Return = {ret:6.2f} | Updated V(S0) = {alpha * ret:5.2f}")96
97lam_val = 0.598lam_ret, details = compute_lambda_return(99    trajectory_rewards, trajectory_states, state_values, discount, 0, lam_val100)101
102print(f"\n=== Compound Lambda-Return (lambda={lam_val}) ===")103for n, g_n, w in details:104    print(f"n={n}: Return = {g_n:6.2f}, Weight = {w:5.3f}, Component = {w*g_n:5.2f}")105print(f"Total G_0^(lambda={lam_val}): {lam_ret:.2f} | Updated V(S0): {alpha * lam_ret:.2f}")106
107# -> === N-Step Returns from State S0 ===108# -> n=1 (TD(0)      ): Return =   4.70 | Updated V(S0) =  0.94109# -> n=2 (2-Step     ): Return =   6.95 | Updated V(S0) =  1.39110# -> n=3 (3-Step     ): Return =  11.97 | Updated V(S0) =  2.39111# -> n=4 (Monte Carlo): Return =  13.43 | Updated V(S0) =  2.69112# -> 113# -> === Compound Lambda-Return (lambda=0.5) ===114# -> n=1: Return =   4.70, Weight = 0.500, Component =  2.35115# -> n=2: Return =   6.95, Weight = 0.250, Component =  1.74116# -> n=3: Return =  11.97, Weight = 0.125, Component =  1.50117# -> n=4: Return =  13.43, Weight = 0.125, Component =  1.68118# -> Total G_0^(lambda=0.5): 7.26 | Updated V(S0): 1.45

Watch Out For

The Quick Version

• Tabular reinforcement learning is a continuous two-dimensional design space governed by backup depth (bootstrapping horizon) and backup width (sample versus distribution).
• One-step TD(0) ($n=1$) and full Monte Carlo ($n=\infty$) are the two extreme boundaries of a single continuous spectrum of $n$-step returns.
• Increasing backup depth $n$ decreases inductive bias from inaccurate bootstrap values but increases sample variance across stochastic transitions.
• The compound $\lambda$-return and eligibility traces ($\text{TD}(\lambda)$) smoothly combine all $n$-step horizons simultaneously, enabling online credit assignment with an optimal bias-variance balance.

What to Read Next

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