N-Step Returns

N-Step returns provide a continuous spectrum between one-step Temporal Difference (TD) learning and full Monte Carlo (MC) returns. The parameter N controls the lookahead horizon:

• N=1: Standard TD(0) update. High bias, low variance.
• N→∞: Equivalent to a full Monte Carlo return. Low bias, high variance.
• 1 < N < ∞: A balanced compromise, using an N-step truncated return plus a bootstrapped estimate of the remainder. This allows the algorithm to be tuned for the specific noise characteristics of the environment.

The core engineering trade-off managed by the N-step parameter is between estimation bias and variance.

• Bias: Introduced by bootstrapping from an imperfect value function. One-step TD has high bias. N-step reduces this bias by incorporating more actual reward signals.
• Variance: Introduced by the stochasticity of future trajectories. Monte Carlo returns have high variance. N-step reduces variance by cutting off the noisy long-term tail and substituting a (presumably less noisy) value estimate. Selecting N is a hyperparameter optimization problem to minimize Mean Squared Error on the value target for a given environment.

N-Step returns are computed in the forward view, requiring the agent to wait N steps to observe the actual rewards before performing an update. The N-step return target G_t:t+n is: G_t:t+n = R_{t+1} + γR_{t+2} + ... + γ^{n-1}R_{t+n} + γ^n V(S_{t+n}) This is implemented in algorithms like N-Step SARSA and N-Step Tree Backup. In practice, this is often combined with an experience replay buffer, where entire trajectories are stored and N-step returns are computed retrospectively during sampling, decoupling learning from the forward view's inherent delay.

N-Step learning is highly synergistic with experience replay. When a transition (S_t, A_t, R_{t+1}, S_{t+1}) is sampled from the buffer, the algorithm can look ahead N-1 steps in the stored trajectory to compute the multi-step target. Key considerations:

• Terminal States: If a terminal state is encountered within the N-step window, the return truncates there (becoming a Monte Carlo return to termination).
• Buffer Storage: Requires storing sequential trajectories, not just independent transitions. This is a core function of a trajectory buffer.
• Prioritized Replay: The Temporal Difference (TD) error of an N-step return can be used for prioritization, focusing replay on transitions where the long-horizon value prediction was inaccurate.

N-Step returns are a special case of the more general TD(λ) method with eligibility traces. TD(λ) efficiently combines all possible N-step returns using an exponential weighting parameter λ.

• The λ-return can be seen as an exponentially weighted average of all N-step returns.
• N-Step is a 'hard' cut-off: It uses a single N. TD(λ) is a 'soft' average: It blends many N values, where λ controls the decay rate.
• Computational Trade-off: Pure N-step methods are simpler but require choosing N. TD(λ) is more complex per update but automatically blends horizons. Modern deep RL often uses a fixed, tuned N (e.g., N=3 or 5 in Rainbow DQN) for simplicity and stability.

In deep reinforcement learning, moving from one-step to multi-step returns is one of the most impactful single improvements.

• Sample Efficiency: By propagating true rewards faster, N-step methods often learn significantly faster than one-step TD.
• Stability: They can stabilize learning in environments with sparse or delayed rewards.
• Typical Values: In dense-reward environments (e.g., Atari), N between 3 and 10 is common. In Rainbow DQN, N=3 is standard. For more stochastic or sparse-reward tasks, larger N may be beneficial.
• Tuning Method: N is typically tuned via grid search, balancing faster learning (larger N) against increased variance and update delay.

The Temporal Difference error is the difference between the estimated value of a state (or state-action pair) and a more accurate, bootstrapped estimate. It is the fundamental signal for credit assignment in reinforcement learning.

• Primary Role: Drives updates to value functions and policies.
• In N-Step Returns: The n-step TD target is used to compute the TD error, which is then minimized.
• Prioritization: In Prioritized Experience Replay (PER), the absolute TD error often determines an experience's sampling probability.

Multi-step learning is the general paradigm of using rewards and state values from multiple future steps to construct a learning target. N-Step Returns are its most common instantiation.

• Spectrum: Unifies one-step TD methods (like Q-learning) and Monte Carlo methods (which use the full return).
• Bias-Variance Trade-off: Increasing n reduces bias (vs. one-step) but increases variance (vs. Monte Carlo).
• Implementation: Used in algorithms like Rainbow DQN and A3C to accelerate propagation of reward signals.

Bootstrapping is the technique of updating estimates based on other existing estimates, rather than waiting for a final outcome. It is a defining characteristic of temporal difference learning.

• Mechanism: N-Step Returns bootstrap by using the value estimate of the state n steps ahead.
• Efficiency: Enables learning online from incomplete sequences without episode termination.
• Trade-off: Introduces bias but significantly reduces variance and speeds learning compared to pure Monte Carlo methods.

The λ-Return provides a continuous blend between TD and Monte Carlo methods by taking a geometrically weighted average of all n-step returns. It is the theoretical foundation of the TD(λ) algorithm.

• Parameter: λ (lambda) in [0,1]. λ=0 gives one-step TD; λ=1 gives Monte Carlo.
• Elegance: Smoothly interpolates the bias-variance trade-off across all possible horizons.
• Practical Use: While computationally expensive to compute exactly, it is approximated efficiently by methods like Eligibility Traces.

Importance sampling is a statistical technique used in off-policy reinforcement learning to correct the bias introduced when learning from experiences generated by a different policy (the behavior policy).

• Core Function: Re-weights the update magnitude of a sampled transition based on the probability ratio between the target and behavior policies.
• N-Step Context: Calculating correct n-step returns for off-policy learning requires importance sampling ratios for each step in the lookahead.
• Algorithms: Essential for off-policy multi-step algorithms like Tree-Backup and Retrace.

V-Trace is an off-policy correction algorithm designed for actor-critic methods, notably used in IMPALA. It computes a corrected, truncated importance-sampled n-step return.

• Key Innovation: Uses truncated importance sampling weights (c_bar and ρ_bar) to provide a trade-off between bias and variance, ensuring stability.
• Target: Produces a v-trace target for the value function, which is a robust off-policy n-step return.
• Application: Enables efficient distributed training where actors use older policies, making experience replay effectively off-policy.