n-Step Returns

Topics: Reinforcement Learning

Overview

Different types of returns can be used to train a critic or perform value estimation in RL.

Monte Carlo returns hand use all the true observed rewards by interacting with the environment starting from a given state:
$y=r_{t+1} + \gamma \; r_{t+2} + \gamma^2 \; r_{t+3} + \gamma ^ 3 \; r_{t+4} + \; ...$
This means that the episode should end and all the reward should be observed before the value of a function is calculated.

Instead of waiting for all the rewards to be observed, single-step Temporal Difference target uses the first observed reward and bootstraps the next state. In other words, it uses one observed reward and the current best estimate for the next state.
$y_{t}=r_{t+1} + \gamma \; V(s_{t+1})$
n-step return is the middle ground between Monte Carlo returns and single-step TD. It consists of observing the next $n$ rewards and then bootstrapping the value estimate.
$y_t=r_{t+1}+ \gamma \; r_{t+2} + \gamma^2 \; r_{t+3} + \; ... \;+ \gamma^n V(s_{t+n})$

Bias vs. Variance

Monte Carlo returns have zero bias theoretically, because the rewards are fully collected from the environment, but can have high variance, especially in stochastic environments. On the other hand, the bootstrap generally has higher bias, because its value could be inaccurate, but has low variance because the critic network returns the same value every time. So, the goal of n-step returns is to balance the bias and variance of the returns, and to improve the value estimation, which subsequently results in a better policy. More on it in Bias & Variance in RL.