Answers.Body: <p>When using terms like "high" for high variance, this is in comparison to other methods, mainly in comparison to TD learning, which bootstraps between single time steps.</p>
  
  <p>It is worth spelling out what the variance applies to and where it comes from: Namely the <em>Monte Carlo return</em> <span class="math-container">$G_t$</span> distribution, which can be calculated as follows:</p>
  
  <p><span class="math-container">$$G_t = \sum_{k=0}^{T-t-1}\gamma^k R_{t+k+1}$$</span></p>
  
  <p>I am using a common convention here by the way that capital letters such as <span class="math-container">$G_t$</span> stand for <em>random distributions</em> of variables and lower case letters such as <span class="math-container">$g_t$</span> stand for examples/samples from those distributions. It is not always strictly used, especially in pseudo-code, but is important to make clear for this answer.</p>
  
  <p>So a value function, such as action value function <span class="math-container">$q_{\pi}(s,a)$</span> can be written:</p>
  
  <p><span class="math-container">$$q_{\pi}(s,a) = \mathbb{E}_{\pi} [ \sum_{k=0}^{T-t-1}\gamma^k R_{t+k+1} | S_t=s, A_t=a] = \mathbb{E}_{\pi} [ G_t | S_t=s, A_t=a]$$</span></p>
  
  <p>i.e. it is fairly clear that the mean of Monte Carlo return <span class="math-container">$\mathbb{E}[G_t]$</span> from any specific starting point is the same as the value function from the same starting point, by definition (see Sutton &amp; Barto or David Silver's definitions) so samples from it - taking specific measures <span class="math-container">$g_t$</span> - are unbiased estimates of it. </p>
  
  <p>The variance <span class="math-container">$\text{Var}(G_t)$</span> might be written</p>
  
  <p><span class="math-container">$$\text{Var}(G_t) = \text{Var}(\sum_{k=0}^{T-t-1}\gamma^k R_{t+k+1}) \le \sum_{k=0}^{T-t-1}\gamma^k \text{Var}(R_{t+k+1})$$</span></p>
  
  <p>The second step is technically equal only in a "worst case" scenario since to add variances directly, we need the variables to be independently sampled, whilst <span class="math-container">$R_{t}$</span> and <span class="math-container">$R_{t+1}$</span> could be correlated, and often are. So, technically we should account for covariance here between distribitions on different time steps. The maths for that is fiddly, and I won't show it here. </p>
  
  <p>What you can say intuitively about the inequality, is unless <span class="math-container">$R_{t}$</span> and <span class="math-container">$R_{t+1}$</span> are perfectly correlated throughout each trajectory, then variance of <span class="math-container">$G_t$</span> will increase depending on the number of timesteps and possible rewards in the return, by some fraction between 0 and 1 of the total variance of all time steps. You can either add zero variance on a timestep, or some fraction of <span class="math-container">$\text{Var}(R_{t+n})$</span> depending on whether the relationship between [<span class="math-container">$R_t$</span> to <span class="math-container">$R_{t+n-1}$</span>] and <span class="math-container">$R_{t+n}$</span> is fully deterministic (<span class="math-container">$+0$</span>) or completely independent (<span class="math-container">$+\gamma^{n-1}\text{Var}(R_{t+n})$</span>)*</p>
  
  <p>The amount of covariance involved relies on details of the policy, state transition and reward functions. In general, the policy during RL will include some stochastic behaviour -such as <span class="math-container">$\epsilon$</span>-greedy that will add to the variance on each time step. The state transition and reward functions <em>might</em> add yet more. In any case:</p>
  
  <p><span class="math-container">$$\text{Var}(G_t) \ge \text{Var}(R_{t+1})$$</span></p>
  
  <p>and in practice, when <span class="math-container">$t+1 \neq T$</span>, the inequality can be large, although highly dependent on the details of the MDP. For off-policy Monte Carlo with basic importance sampling in fact the variance can be unbounded.</p>
  
  <p>This variance might be considered high, compared to the variance of typical single-step TD returns:</p>
  
  <p><span class="math-container">$$G_{t:t+1} = R_{t+1} + \gamma q_{\pi}(S_t, A_t)$$</span></p>
  
  <p>The variance of which is limited to that inherent in a single time step (one reward function, one state transition and one policy decision). The problem of course being that </p>
  
  <p><span class="math-container">$$\mathbb{E}[G_{t:t+1}] \neq \mathbb{E}[G_{t}]$$</span></p>
  
  <p>. . . unless <span class="math-container">$q_{\pi}(s, a)$</span> is perfect. Which is why we can say that TD returns are biased (<em>whilst <span class="math-container">$q_{\pi}(s, a)$</span> is not converged, the expectation of the TD target does not equal the true value</em>), but Monte Carlo returns are higher variance (<em>when number of timesteps to end of trajectory is more than one, the effects of random factors in policy, state transition and reward function accumulate</em>).</p>
  
  <hr>
  
  <p>* You could explicitly construct an environment with covariance between time steps that can reduce overall variance of a MDP's retrun, e.g. the state includes reward so far, and future rewards are manipulated so that the return fits to a certain distribution. This would be a special case where variance of the return from <em>some</em> starting points could be lower than the variance from the first step, but this is an unusual set up and likely to be impossible for an agent to learn optimal control. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-03T17:36:11.937Z
Answers.Text: You say "it is fairly clear that the mean of Monte Carlo return...is the same as the value function from the same starting point", but I don't think this is "clear", in the sense that, unless you know the definition of the state-action value function, then this is not clear. You also say "What you can say intuitively about the inequality...", but this is not intuitive at all (at least to me, in the way you describe it). I guess you're saying this because you suppose that the variance of a bigger sum becomes larger.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-03T17:39:11.690Z
Answers.Text: You also then say "by some fraction between 0 and 1 of the total variance of all time steps", but I am not sure what you're talking about. Furthermore, you use the notation $\sigma^2(X)$ to denote the variance. Maybe the notation $\text{Var}(X)$ would be more intuitive. You also use both $\mathbb{E}$ and $\mu$, which makes things more confusing, if you are not familiar with all the notation (not my case). You may also attempt to expand the definition of $\text{Var}(X)$ in terms of the expectation and see what comes out of it (I haven't tried it).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-03T19:22:46.943Z
Answers.Text: @nbro: The variance of a sum of independent variables is equal to the sum of the variances of the variables. In an RL trajectory, the variables are not independent, but they are often at least partially independent.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-03T19:31:32.943Z
Answers.Text: @nbro I am changing the notation as suggested. OP is already happy with unbiased nature of Monte Carlo estimate, so I am just mentioning that in passing. You are right it is because $v_{\pi}(s) = \mathbb{E}_{\pi}[G_t|S_t = s]$ by definition (and similar for $q_{\pi}$), and I have already written answers about that so may link one
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-03T22:26:40.347Z
Answers.Text: Ok, thanks for addressing this. After re-reading this answer, I think you should also use either the expression "random variable" or "probability distribution" and not "variable distribution" (which I've never heard of, unless it really refers to a distribution that varies, which can be the case, but I think you didn't mean that).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-03T13:18:47.480Z
Answers.LastActivityDate: 2020-02-04T07:30:00.203Z
Answers.LastEditDate: 2020-02-04T07:30:00.203Z
Answers.UserDisplayName: Neil Slater
Body: <p>I was going through David Silver's lecture on reinforcement learning (lecture 4). At 51:22 he says that Monte Carlo (MC) methods have high variance and zero bias. I understand the zero bias part. It is because it is using the true value of value function for estimation. However, I don't understand the high variance part. Can someone enlighten me?</p>
  
Tags: <reinforcement-learning><monte-carlo-methods><temporal-difference-methods><bias-variance-tradeoff>
Title: How does Monte Carlo have high variance?
UserDisplayName: Bhuwan Bhatt
ThreadText: # How does Monte Carlo have high variance?
  
  (Asked by: username_0 on 2020-02-03)
  
  I was going through David Silver's lecture on reinforcement learning (lecture 4). At 51:22 he says that Monte Carlo (MC) methods have high variance and zero bias. I understand the zero bias part. It is because it is using the true value of value function for estimation. However, I don't understand the high variance part. Can someone enlighten me?
  
  **Tags:** reinforcement-learning, monte-carlo-methods, temporal-difference-methods, bias-variance-tradeoff
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-02-03. Score: 2
  
  When using terms like "high" for high variance, this is in comparison to other methods, mainly in comparison to TD learning, which bootstraps between single time steps.
  
  It is worth spelling out what the variance applies to and where it comes from: Namely the *Monte Carlo return* $G\_t$ distribution, which can be calculated as follows:
  
  $$G\_t = \sum\_{k=0}^{T-t-1}\gamma^k R\_{t+k+1}$$
  
  I am using a common convention here by the way that capital letters such as $G\_t$ stand for *random distributions* of variables and lower case letters such as $g\_t$ stand for examples/samples from those distributions. It is not always strictly used, especially in pseudo-code, but is important to make clear for this answer.
  
  So a value function, such as action value function $q\_{\pi}(s,a)$ can be written:
  
  $$q\_{\pi}(s,a) = \mathbb{E}\_{\pi} [ \sum\_{k=0}^{T-t-1}\gamma^k R\_{t+k+1} | S\_t=s, A\_t=a] = \mathbb{E}\_{\pi} [ G\_t | S\_t=s, A\_t=a]$$
  
  i.e. it is fairly clear that the mean of Monte Carlo return $\mathbb{E}[G\_t]$ from any specific starting point is the same as the value function from the same starting point, by definition (see Sutton & Barto or David Silver's definitions) so samples from it - taking specific measures $g\_t$ - are unbiased estimates of it.
  
  The variance $\text{Var}(G\_t)$ might be written
  
  $$\text{Var}(G\_t) = \text{Var}(\sum\_{k=0}^{T-t-1}\gamma^k R\_{t+k+1}) \le \sum\_{k=0}^{T-t-1}\gamma^k \text{Var}(R\_{t+k+1})$$
  
  The second step is technically equal only in a "worst case" scenario since to add variances directly, we need the variables to be independently sampled, whilst $R\_{t}$ and $R\_{t+1}$ could be correlated, and often are. So, technically we should account for covariance here between distribitions on different time steps. The maths for that is fiddly, and I won't show it here.
  
  What you can say intuitively about the inequality, is unless $R\_{t}$ and $R\_{t+1}$ are perfectly correlated throughout each trajectory, then variance of $G\_t$ will increase depending on the number of timesteps and possible rewards in the return, by some fraction between 0 and 1 of the total variance of all time steps. You can either add zero variance on a timestep, or some fraction of $\text{Var}(R\_{t+n})$ depending on whether the relationship between [$R\_t$ to $R\_{t+n-1}$] and $R\_{t+n}$ is fully deterministic ($+0$) or completely independent ($+\gamma^{n-1}\text{Var}(R\_{t+n})$)\*
  
  The amount of covariance involved relies on details of the policy, state transition and reward functions. In general, the policy during RL will include some stochastic behaviour -such as $\epsilon$-greedy that will add to the variance on each time step. The state transition and reward functions *might* add yet more. In any case:
  
  $$\text{Var}(G\_t) \ge \text{Var}(R\_{t+1})$$
  
  and in practice, when $t+1 \neq T$, the inequality can be large, although highly dependent on the details of the MDP. For off-policy Monte Carlo with basic importance sampling in fact the variance can be unbounded.
  
  This variance might be considered high, compared to the variance of typical single-step TD returns:
  
  $$G\_{t:t+1} = R\_{t+1} + \gamma q\_{\pi}(S\_t, A\_t)$$
  
  The variance of which is limited to that inherent in a single time step (one reward function, one state transition and one policy decision). The problem of course being that
  
  $$\mathbb{E}[G\_{t:t+1}] \neq \mathbb{E}[G\_{t}]$$
  
  . . . unless $q\_{\pi}(s, a)$ is perfect. Which is why we can say that TD returns are biased (*whilst $q\_{\pi}(s, a)$ is not converged, the expectation of the TD target does not equal the true value*), but Monte Carlo returns are higher variance (*when number of timesteps to end of trajectory is more than one, the effects of random factors in policy, state transition and reward function accumulate*).
  
  ---
  
  \* You could explicitly construct an environment with covariance between time steps that can reduce overall variance of a MDP's retrun, e.g. the state includes reward so far, and future rewards are manipulated so that the return fits to a certain distribution. This would be a special case where variance of the return from *some* starting points could be lower than the variance from the first step, but this is an unusual set up and likely to be impossible for an agent to learn optimal control.
  
  > **Comments:**
  > **username_2**: You say "it is fairly clear that the mean of Monte Carlo return...is the same as the value function from the same starting point", but I don't think this is "clear", in the sense that, unless you know the definition of the state-action value function, then this is not clear. You also say "What you can say intuitively about the inequality...", but this is not intuitive at all (at least to me, in the way you describe it). I guess you're saying this because you suppose that the variance of a bigger sum becomes larger.  
  > **username_2**: You also then say "by some fraction between 0 and 1 of the total variance of all time steps", but I am not sure what you're talking about. Furthermore, you use the notation $\sigma^2(X)$ to denote the variance. Maybe the notation $\text{Var}(X)$ would be more intuitive. You also use both $\mathbb{E}$ and $\mu$, which makes things more confusing, if you are not familiar with all the notation (not my case). You may also attempt to expand the definition of $\text{Var}(X)$ in terms of the expectation and see what comes out of it (I haven't tried it).  
  > **username_1**: @username_2: The variance of a sum of independent variables is equal to the sum of the variances of the variables. In an RL trajectory, the variables are not independent, but they are often at least partially independent.  
  > **username_1**: @username_2 I am changing the notation as suggested. OP is already happy with unbiased nature of Monte Carlo estimate, so I am just mentioning that in passing. You are right it is because $v_{\pi}(s) = \mathbb{E}_{\pi}[G_t|S_t = s]$ by definition (and similar for $q_{\pi}$), and I have already written answers about that so may link one  
  > **username_2**: Ok, thanks for addressing this. After re-reading this answer, I think you should also use either the expression "random variable" or "probability distribution" and not "variable distribution" (which I've never heard of, unless it really refers to a distribution that varies, which can be the case, but I think you didn't mean that).  
  
  ---
  
  