5
$\begingroup$

I'm studying Reinforcement learning from lectures of David Silver, where he says that Monte Carlo method is not biased and has very high variance. But I don't understand in which sense the bias and variance are defined.

In this article the reason behind high variance is explained as:

The fact that we are taking many steps before finishing an episode and only then updating our estimates introduces a high amount of variance into the updates.

But can anyone give an intuitive example of this type of scenario? I also don't understand how Monte Carlo method is not biased.

$\endgroup$
2
  • $\begingroup$ Regarding "I also don't understand how Monte Carlo method is not biased." could you explain why you think it would be biased? $\endgroup$ – Neil Slater Sep 1 '18 at 19:13
  • 1
    $\begingroup$ Actually I don't know how to determine whether it's bias or unbiased. I just want to know some intuitive terminology about both bias and variance if possible. $\endgroup$ – Kaushal28 Sep 1 '18 at 20:15
7
$\begingroup$

In RL, for value functions, the bias and variance refer to behaviour of different kinds of estimate for the value function. The value function's true value is the expected return from a specific starting state (and action for action values), assuming that all actions are selected according to the policy being evaluated. For control problems you can just aim for the optimal policy, but the bias and variance are considered with respect to the current "best guess" at the policy. For Monte Carlo control, that is either greedy policy with respect to current Q estimates, or $\epsilon$-greedy with respect to same (for off-policy and on-policy control respectively).

The definition of the action value function is

$$Q_{\pi}(s,a) = \mathbb{E}_{\pi}[G_t | S_t=s, A_t=a] = \mathbb{E}_{\pi}[\sum_{k=0}^{\infty}\gamma^k R_{t+k+1} | S_t=s, A_t=a]$$

From this we can see, almost trivially, that Monte Carlo estimates are unbiased. That is because a single Monte Carlo estimate is given by

$$\hat{q}(s_t,a_t) = \sum_{k=0}^{\infty}\gamma^k r_{t+k+1}$$

It is clearly a sample of the same stochastic function given by the definition of Q. It is unbiased in the same way that a roll of a die is an unbiased estimate of the expected result of rolling that die.

Variance is slightly trickier. Fundamentally, the variance is high because the return is the sum of many random variables ($R_t ... \gamma^{T-t}R_T$, each of which depends on distributions not just in reward $R$, but also in the choice of action $A$ by the policy, and state transition dynamics that pick each $S$) and the variance of a sum is the sum of the variance when the variables are independent - however in RL, the sequence of $R_t$ can be highly correlated. The correlation is not guaranteed by the form of the MDP in general, but it can often be the case. As a result, I don't think you will find a general formula for variance of Monte Carlo estimates of Q, and the argument is more about intuition and empirical data.

It is easier to see that variance of Monte Carlo is higher in general than the variance of one-step Temporal Difference methods. The formula for a basic TD Target (equivalent to the return $G_t$ from Monte Carlo) is

$$\hat{q}(s_t,a_t) = r_{t+1} + \gamma \hat{q}(s_{t+1},a_{t+1})$$

This has only a fixed number of three random variables that have been sampled from the single step being used. Therefore you can expect it to have proportionally less variance than any Monte Carlo estimate based on a longer trajectory. The big problem with it is reliance on the estimate $\hat{q}$, because during the learning process this is very unlikely to be a perfect estimate. In fact it is biased towards whatever the starting values were for $\hat{q}$, which is typically either zero for simple estimation functions, or random such as when dealing with neural networks. That said, often the low variance is a deciding factor and TD learning will require less training data than Monte Carlo on the same problem.

$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.