Answers.Body: <p>If you simulate many trajectories and receive many estimates of the two returns you're interested in, you could empirically compare their <a href="https://en.wikipedia.org/wiki/Variance#Sample_variance" rel="nofollow noreferrer">sample variances</a>.</p>
  
  <p>However, the variance of ordinary importance sampling is in general unbounded.
  If you're wanting some theoretical bounds on the variance of importance sampling estimates, I'd start with <em>weighted importance sampling</em>, whose variance converges to zero (<a href="http://incompleteideas.net/book/the-book-2nd.html" rel="nofollow noreferrer">Sutton and Barto</a>, section 5.5). </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-06T10:08:16.690Z
Answers.LastActivityDate: 2019-03-06T10:08:16.690Z
Answers.UserDisplayName: Philip Raeisghasem
Body: <p>Suppose there is an evaluation policy called <span class="math-container">$\pi_{e}$</span> and there are two behavior policies <span class="math-container">$\pi_{b1}$</span> and <span class="math-container">$\pi_{b2}$</span>. I know that it is possible to estimate the return of policy <span class="math-container">$\pi_{e}$</span> through behavior policies via <em>importance sampling</em>, which is unbiased. But I do not know about the variance of return estimated through two behavior policies <span class="math-container">$\pi_{b1}$</span> and <span class="math-container">$\pi_{b2}$</span>. Does anybody know about the variance or any bound on the variance of estimated return?</p>
  
  <p>Let <span class="math-container">$G_{0}^{b1}=\sum_{t=1}^{T}\gamma^{t-1}r_{t}^{b1}$</span> represent the total return for an episode through behavior policy <span class="math-container">$\pi_{b1}$</span> and <span class="math-container">$G_{0}^{b2}=\sum_{t=1}^{T}\gamma^{t-1}r_{t}^{b2}$</span> represent the total return for an episode through behavior policy <span class="math-container">$\pi_{b2}$</span>.
  It is possible to estimate the return of policy <span class="math-container">$\pi_{e}$</span> as follows:</p>
  
  <p><span class="math-container">$$G_{0}^{(e,b1)}=\prod_{t=1}^{T}\frac{\pi_{e}(a_{t}|s_{t})}{\pi_{b1}(a_{t}|s_{t})}*G_{0}^{b1}$$</span></p>
  
  <p><span class="math-container">$$G_{0}^{(e,b2)}=\prod_{t=1}^{T}\frac{\pi_{e}(a_{t}|s_{t})}{\pi_{b2}(a_{t}|s_{t})}*G_{0}^{b2}$$</span></p>
  
  <p>I want to compare the variance of <span class="math-container">$G_{0}^{(e,b1)}$</span> and <span class="math-container">$G_{0}^{(e,b2)}$</span>. Is there any formulation to compute the variance <span class="math-container">$G_{0}^{(e,b1)}$</span> and <span class="math-container">$G_{0}^{(e,b2)}$</span>?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-17T20:00:04.203Z
Comments.Text: Perhaps give a formula or notes on a variance that you do know how to obtain in the question, so that someone answering can use the same notation, and understands where to start from so that you will understand
Comments.UserDisplayName: Neil Slater
Tags: <reinforcement-learning><policies><off-policy-methods>
Title: How do I compute the variance of the return of an evaluation policy using two behaviour policies?
UserDisplayName: Amin
ThreadText: # How do I compute the variance of the return of an evaluation policy using two behaviour policies?
  
  (Asked by: username_0 on 2019-01-17)
  
  Suppose there is an evaluation policy called $\pi\_{e}$ and there are two behavior policies $\pi\_{b1}$ and $\pi\_{b2}$. I know that it is possible to estimate the return of policy $\pi\_{e}$ through behavior policies via *importance sampling*, which is unbiased. But I do not know about the variance of return estimated through two behavior policies $\pi\_{b1}$ and $\pi\_{b2}$. Does anybody know about the variance or any bound on the variance of estimated return?
  
  Let $G\_{0}^{b1}=\sum\_{t=1}^{T}\gamma^{t-1}r\_{t}^{b1}$ represent the total return for an episode through behavior policy $\pi\_{b1}$ and $G\_{0}^{b2}=\sum\_{t=1}^{T}\gamma^{t-1}r\_{t}^{b2}$ represent the total return for an episode through behavior policy $\pi\_{b2}$.
  It is possible to estimate the return of policy $\pi\_{e}$ as follows:
  
  $$G\_{0}^{(e,b1)}=\prod\_{t=1}^{T}\frac{\pi\_{e}(a\_{t}|s\_{t})}{\pi\_{b1}(a\_{t}|s\_{t})}\*G\_{0}^{b1}$$
  
  $$G\_{0}^{(e,b2)}=\prod\_{t=1}^{T}\frac{\pi\_{e}(a\_{t}|s\_{t})}{\pi\_{b2}(a\_{t}|s\_{t})}\*G\_{0}^{b2}$$
  
  I want to compare the variance of $G\_{0}^{(e,b1)}$ and $G\_{0}^{(e,b2)}$. Is there any formulation to compute the variance $G\_{0}^{(e,b1)}$ and $G\_{0}^{(e,b2)}$?
  
  **Tags:** reinforcement-learning, policies, off-policy-methods
  
  > **Comments:**
  > **username_1**: Perhaps give a formula or notes on a variance that you do know how to obtain in the question, so that someone answering can use the same notation, and understands where to start from so that you will understand  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2019-03-06. Score: 1
  
  If you simulate many trajectories and receive many estimates of the two returns you're interested in, you could empirically compare their [sample variances](https://en.wikipedia.org/wiki/Variance#Sample_variance).
  
  However, the variance of ordinary importance sampling is in general unbounded.
  If you're wanting some theoretical bounds on the variance of importance sampling estimates, I'd start with *weighted importance sampling*, whose variance converges to zero ([Sutton and Barto](http://incompleteideas.net/book/the-book-2nd.html), section 5.5).
  
  
  ---
  
  