Bias & Variance in RL

Topics: Reinforcement Learning

Bias vs. Variance

The question of bias vs. variance arises in RL when comparing Monte Carlo and bootstrapped targets for critic regression. The critic learns the state value $V(s)$ or or state-action value $Q(s,a)$, which are expected sums of discounted rewards.

With Monte Carlo returns, actual rollouts are performed in the environment and the discounted sum of the obtained rewards over a horizon $H$ is used as a regression target:
$V_{MC}(s) = \sum_{n=0}^H \gamma^n r_n$
Monte Carlo targets have low bias, effectively 0, but high variance. This is because the rewards are obtained from the environment itself, so, their expectation is the true value. The variance is high in stochastic environments because the rewards are a distribution over states and actions; so, even for the same trajectories, different rewards can be obtained. This is not the case in purely deterministic environments, where the Monte Carlo returns have low bias and variance.

On the other hand, the 1-step Temporal Difference bootstrapped targets, like the ones in DDPG, TD3 and SAC, have high bias but low variance. For a given state $s$ or $(s,a)$ pair, the output of the target value network is constant (low variance), but is often deviated from the true value (high bias).
$V_{TD}(s) = r+\gamma V(s')$

Balancing Bias and Variance

To balance bias and variance, the common approach is to include a mix of Monte Carlo and bootstrapping.
For model-free methods, n-step bootstrapping is employed, where actual rewards are added for the first $H$ steps, followed by a discounted value estimate:
$V_N(s) = \sum_{n=0}^{H-1} \gamma^n r_n + \gamma^H V(s')$
For model-based methods, where the agent can perform imaginary rollouts without interacting with the environment, (1) suggests an exponentially-weighted average of n-step lengths to balance bias and variance:
$V_{\lambda}(s) = (1-\lambda) \sum_{n=1}^{H-1} \lambda^{n-1}V_N^n(s) + \lambda^{H-1}V_N^H(s)$
It is basically a convex combination between the n-step value estimates at different lengths. The parameter $\lambda \in [0,1]$ controls the weight tradeoff between short and long MC horizon: as $\lambda \rightarrow 0$, shorter horizons are weighted more, and as $\lambda \rightarrow 1$, longer horizons are weighted more. $\lambda=0$ reduces to a pure 1-step TD target, while $\lambda=1$ reduces to a single n-step return over the horizon $H$.
Looking at it from another perspective, $\lambda$ allows to control the level of trust in the learned model. With longer $\lambda$, the equation leans more towards longer horizon MC return, meaning that it trusts the model's multi-step predictions, while still blending some bootstrap values.

References

1. D. Hafner, T. Lillicrap, J. Ba, and M. Norouzi, “Dream to Control: Learning Behaviors by Latent Imagination,” Mar. 17, 2020, arXiv: arXiv:1912.01603. doi: 10.48550/arXiv.1912.01603.