Answers.Body: <p><strong>First Part</strong></p>
  <p>We can reduce variance in off-policy importance sapling, even in the absence of discounting (<span class="math-container">$\gamma = 1$</span>). Notice that the off-policy estimators are made up of terms like
  <span class="math-container">$$\rho_{t:T-1}G_t = \rho_{t:T-1} (R_{t+1} + \gamma R_{t+2} + \dots+ \gamma^{T-t-1}R_{T})$$</span></p>
  <p>and consider the second term, imagine <span class="math-container">$\gamma$</span>=<span class="math-container">$1$</span>:
  <span class="math-container">$$\rho_{t:T-1}R_{t+2} = \frac{\pi(A_t|S_t) \pi(A_{t+1}|S_{t+1})......\pi(A_{T-1}|S_{T-1})}{b(A_t|S_t) b(A_{t+1}|S_{t+1})...... b(A_{T-1}|S_{T-1})} R_{t+2}$$</span>
  In above equation, the term <span class="math-container">$\pi(A_t|S_t)$</span>, <span class="math-container">$\pi(A_{t+1}|S_{t+1})$</span>, <span class="math-container">$R_{t+2}$</span> are correleated, all the other terms are independent of each other.</p>
  <p>Notice the very import property of expectation:
  <span class="math-container">$E[ab] = E[a] E[b]$</span> if and only if <span class="math-container">$a$</span>, <span class="math-container">$b$</span> are independent random variables.</p>
  <p>Now:
  <span class="math-container">$$  E[\frac{\pi(A_t|S_t) \pi(A_{t+1}|S_{t+1}).....\pi(A_{T-1}|S_{T-1})}{b(A_t|S_t) b(A_{t+1}|S_{t+1}).....b(A_{T-1}|S_{T-1})} R_{t+2}]$$</span>
  <span class="math-container">$$  = E[\frac{\pi(A_t|S_t) \pi(A_{t+1}|S_{t+1})}{b(A_t|S_t) b(A_{t+1}|S_{t+1})} R_{t+2}]  E[\frac{\pi(A_{t+2}|S_{t+2})}{b(A_{t+2}|S_{t+2})}] .....  E[\frac{\pi(A_{T-1}|S_{T-1})}{b(A_{T-1}|S_{T-1})}]$$</span>
  <span class="math-container">$$ = E[\frac{\pi(A_t|S_t) \pi(A_{t+1}|S_{t+1})}{b(A_t|S_t) b(A_{t+1}|S_{t+1})} R_{t+2}] \sum_a b(a|s_{t+2}) \frac{\pi(a|s_{t+2}}{b(a|s_{t+2}}.....\sum_a b(a|s_{T-1}) \frac{\pi(a|s_{T-1}}{b(a|s_{T-1}} $$</span>
  <span class="math-container">$$ = E[\frac{\pi(A_t|S_t) \pi(A_{t+1}|S_{t+1})}{b(A_t|S_t) b(A_{t+1}|S_{t+1})} R_{t+2}] \sum_a \pi(a|s_{t+2}).....\sum_a \pi(a|s_{T-1})$$</span><br />
  <span class="math-container">$$ = E[\frac{\pi(A_t|S_t) \pi(A_{t+1}|S_{t+1})}{b(A_t|S_t) b(A_{t+1}|S_{t+1})} R_{t+2}] 1 * 1  $$</span>
  <span class="math-container">$$ = E[\frac{\pi(A_t|S_t) \pi(A_{t+1}|S_{t+1})}{b(A_t|S_t) b(A_{t+1}|S_{t+1})} R_{t+2}]  $$</span>
  therefore
  <span class="math-container">$$  E[\rho_{t:T-1}R_{t+2}] = E[\rho_{t:t+1} R_{t+2}]$$</span>
  If we repeat this analysis for the <span class="math-container">$k$</span>th term, we will get:
  <span class="math-container">$$E[\rho_{t:T-1}R_{t+k}] = E[\rho_{t:t+k-1} R_{t+k}]$$</span>
  It follows that the expectation of our original term can be written:
  <span class="math-container">$$E[\rho_{t:T-1}G_{t}] = E[\tilde{G_{t}}]$$</span>
  where
  <span class="math-container">$$\tilde{G}_t \doteq \rho_{t:t}R_{t+1} + \gamma \rho_{t:t+1}R_{t+2} + \gamma^{2} \rho_{t:t+2}R_{t+3} + ...... + \gamma^{T-t-1} \rho_{t:T-1}R_{T}$$</span>
  We call this idea per reward importance sampling. It follows immediately that there is an alternative importance sampling estimate, with the same unbiased expectation as the ordinary importance sampling estimate:
  <span class="math-container">$$V(s) \doteq \frac{\sum_{t\in\mathcal{T}(s)} \tilde{G}_t}{|\mathcal{T}(s)|}$$</span>
  which we might expect to sometimes be of lower variance.</p>
  <p><strong>Second Part</strong></p>
  <p>The reward <span class="math-container">$R_{k+1}$</span> depends on the previous <span class="math-container">$\pi(a_1|s_1)$</span> up to <span class="math-container">$\pi(a_{k-1}|s_{k-1})$</span>. So, you can't seperate them and treat them as independent variable just you did on the aforementioned example.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-11T10:41:44.953Z
Answers.LastActivityDate: 2020-09-11T10:54:21.943Z
Answers.LastEditDate: 2020-09-11T10:54:21.943Z
Answers.UserDisplayName: Swakshar Deb
Body: <p>In per-decison importance sampling given in <a href="http://incompleteideas.net/book/RLbook2020.pdf#page=136" rel="nofollow noreferrer">Sutton &amp; Barto's book</a>:</p>
  
  <blockquote>
    <p>Eq 5.12 <span class="math-container">$\rho_{t:T-1}R_{t+k} = \frac{\pi(A_{t}|S_{t})}{b(A_{t}|S_{t})}\frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})}\frac{\pi(A_{t+2}|S_{t+2})}{b(A_{t+2}|S_{t+2})}......\frac{\pi(A_{T-1}|S_{T-1})}{b(A_{T-1}|S_{T-1})}R_{t+k}$</span></p>
    
    <p>Eq 5.13 <span class="math-container">$\mathbb{E}\left[\frac{\pi(A_{k}|S_{k})}{b(A_{k}|S_{k})}\right] = \displaystyle\sum_ab(a|S_k)\frac{\pi(A_{k}|S_{k})}{b(A_{k}|S_{k})} = \displaystyle\sum_a\pi(a|S_k) = 1$</span></p>
    
    <p>Eq.5.14 <span class="math-container">$\mathbb{E}[\rho_{t:T-1}R_{t+k}] = \mathbb{E}[\rho_{t:t+k-1}R_{t+k}]$</span></p>
  </blockquote>
  
  <p>As full derivation is not given, how do we arrive at Eq 5.14 from 5.12?</p>
  
  <h3>From what i understand :</h3>
  
  <p>1) <span class="math-container">$R_{t+k}$</span> is only dependent on action taken at <span class="math-container">$t+k-1$</span> given state at that time i.e. only dependent on <span class="math-container">$\frac{\pi(A_{t+k-1}|S_{t+k-1})}{b(A_{t+k-1}|S_{t+k-1})}$</span>  </p>
  
  <p>2) <span class="math-container">$\frac{\pi(A_{k}|S_{k})}{b(A_{k}|S_{k})}$</span> is independent of <span class="math-container">$\frac{\pi(A_{k+1}|S_{k+1})}{b(A_{k+1}|S_{k+1})}$</span> , so <span class="math-container">$\mathbb{E}\left[\frac{\pi(A_{k}|S_{k})}{b(A_{k}|S_{k})}\frac{\pi(A_{k+1}|S_{k+1})}{b(A_{k+1}|S_{k+1})}\right] = \mathbb{E}\left[\frac{\pi(A_{k}|S_{k})}{b(A_{k}|S_{k})}\right]\mathbb{E}\left[\frac{\pi(A_{k+1}|S_{k+1})}{b(A_{k+1}|S_{k+1})}\right], \forall \, k\in [t,T-2]$</span></p>
  
  <p>Hence, <span class="math-container">$\mathbb{E}[\rho_{t:T-1}R_{t+k}]= \mathbb{E}\left[\frac{\pi(A_{t}|S_{t})}{b(A_{t}|S_{t})}\frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})}\frac{\pi(A_{t+2}|S_{t+2})}{b(A_{t+2}|S_{t+2})}......\frac{\pi(A_{T-1}|S_{T-1})}{b(A_{T-1}|S_{T-1})}R_{t+k}\right] \\= \mathbb{E}\left[\frac{\pi(A_{t}|S_{t})}{b(A_{t}|S_{t})}\frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})}\frac{\pi(A_{t+2}|S_{t+2})}{b(A_{t+2}|S_{t+2})}....\frac{\pi(A_{t+k-2}|S_{t+k-2})}{b(A_{t+k-2}|S_{t+k-2})}\frac{\pi(A_{t+k}|S_{t+k})}{b(A_{t+k}|S_{t+k})}......\frac{\pi(A_{T-1}|S_{T-1})}{b(A_{T-1}|S_{T-1})}\right]\mathbb{E}\left[\frac{\pi(A_{t+k-1}|S_{t+k-1})}{b(A_{t+k-1}|S_{t+k-1})}R_{t+k}\right] \\= \mathbb{E}\left[\frac{\pi(A_{t}|S_{t})}{b(A_{t}|S_{t})}\right]\mathbb{E}\left[\frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})}\right]\mathbb{E}\left[\frac{\pi(A_{t+2}|S_{t+2})}{b(A_{t+2}|S_{t+2})}\right]....\mathbb{E}\left[\frac{\pi(A_{t+k-2}|S_{t+k-2})}{b(A_{t+k-2}|S_{t+k-2})}\right]\mathbb{E}\left[\frac{\pi(A_{t+k}|S_{t+k})}{b(A_{t+k}|S_{t+k})}\right]......\mathbb{E}\left[\frac{\pi(A_{T-1}|S_{T-1})}{b(A_{T-1}|S_{T-1})}\right]\mathbb{E}\left[\frac{\pi(A_{t+k-1}|S_{t+k-1})}{b(A_{t+k-1}|S_{t+k-1})}R_{t+k}\right] \\= \mathbb{E}[\frac{\pi_{t+k-1}}{b_{t+k-1}}R_{t+k}]\\=\mathbb{E}[\rho_{t+k-1}R_{t+k}]$</span> </p>
  
  <h3>which is not equal to eq 5.14. What's the mistake in the above calculations? Are 1 and 2 correct?</h3>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-13T16:50:40.400Z
Comments.Text: To answer your last question, in general, the expectation of the product of two random variables is not equal to the product of the expectations of each random variable, unless the random variables are independent. That doesn't seem to be true in your case (given that the policies at successive time steps could be correlated), but I could be wrong (because I know little or almost nothing about importance sampling and related topics).
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-13T22:17:05.997Z
Comments.Text: I don't think policies at successive time steps are correlated, otherwise there would have been no point of giving eq 5.13. Also in theory given in the book, $\pi$ is sometimes taken as epsilon-greedy which is not correlated
Comments.UserDisplayName: ZERO NULLS
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-14T08:06:00.267Z
Comments.Text: You made a mistake in step 2. State $S_{k+1}$ depends on $S_k$ and $A_k$ through conditional probability $p(s'|s,a)$ so you cant do what you did.
Comments.UserDisplayName: Brale
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-14T22:07:44.743Z
Comments.Text: $S_{k+1}$ is indeed dependent on $S_k$ but $A_k|S_k $ is independent of $A_{k+1}|S_{k+1}$ because $P(A_k|S_k)$ means, given $S_k = s$, what's the probability of choosing $A_k = a$ , similarly for $P(A_{k+1}|S_{k+1})$ . Hence since we are given $S_{k+1} = s'$, there is no need to calculate $p(s'|s,a)$. Is something wrong in this way of thinking??
Comments.UserDisplayName: ZERO NULLS
Tags: <reinforcement-learning><off-policy-methods><expectation><importance-sampling><conditional-probability>
Title: How is per-decision importance sampling derived in Sutton & Barto's book?
UserDisplayName: ZERO NULLS
ThreadText: # How is per-decision importance sampling derived in Sutton & Barto's book?
  
  (Asked by: username_0 on 2020-06-13)
  
  In per-decison importance sampling given in [Sutton & Barto's book](http://incompleteideas.net/book/RLbook2020.pdf#page=136):
  
  > Eq 5.12 $\rho\_{t:T-1}R\_{t+k} = \frac{\pi(A\_{t}|S\_{t})}{b(A\_{t}|S\_{t})}\frac{\pi(A\_{t+1}|S\_{t+1})}{b(A\_{t+1}|S\_{t+1})}\frac{\pi(A\_{t+2}|S\_{t+2})}{b(A\_{t+2}|S\_{t+2})}......\frac{\pi(A\_{T-1}|S\_{T-1})}{b(A\_{T-1}|S\_{T-1})}R\_{t+k}$
  >
  > Eq 5.13 $\mathbb{E}\left[\frac{\pi(A\_{k}|S\_{k})}{b(A\_{k}|S\_{k})}\right] = \displaystyle\sum\_ab(a|S\_k)\frac{\pi(A\_{k}|S\_{k})}{b(A\_{k}|S\_{k})} = \displaystyle\sum\_a\pi(a|S\_k) = 1$
  >
  > Eq.5.14 $\mathbb{E}[\rho\_{t:T-1}R\_{t+k}] = \mathbb{E}[\rho\_{t:t+k-1}R\_{t+k}]$
  
  As full derivation is not given, how do we arrive at Eq 5.14 from 5.12?
  
  ### From what i understand :
  
  1) $R\_{t+k}$ is only dependent on action taken at $t+k-1$ given state at that time i.e. only dependent on $\frac{\pi(A\_{t+k-1}|S\_{t+k-1})}{b(A\_{t+k-1}|S\_{t+k-1})}$
  
  2) $\frac{\pi(A\_{k}|S\_{k})}{b(A\_{k}|S\_{k})}$ is independent of $\frac{\pi(A\_{k+1}|S\_{k+1})}{b(A\_{k+1}|S\_{k+1})}$ , so $\mathbb{E}\left[\frac{\pi(A\_{k}|S\_{k})}{b(A\_{k}|S\_{k})}\frac{\pi(A\_{k+1}|S\_{k+1})}{b(A\_{k+1}|S\_{k+1})}\right] = \mathbb{E}\left[\frac{\pi(A\_{k}|S\_{k})}{b(A\_{k}|S\_{k})}\right]\mathbb{E}\left[\frac{\pi(A\_{k+1}|S\_{k+1})}{b(A\_{k+1}|S\_{k+1})}\right], \forall \, k\in [t,T-2]$
  
  Hence, $\mathbb{E}[\rho\_{t:T-1}R\_{t+k}]= \mathbb{E}\left[\frac{\pi(A\_{t}|S\_{t})}{b(A\_{t}|S\_{t})}\frac{\pi(A\_{t+1}|S\_{t+1})}{b(A\_{t+1}|S\_{t+1})}\frac{\pi(A\_{t+2}|S\_{t+2})}{b(A\_{t+2}|S\_{t+2})}......\frac{\pi(A\_{T-1}|S\_{T-1})}{b(A\_{T-1}|S\_{T-1})}R\_{t+k}\right] \\= \mathbb{E}\left[\frac{\pi(A\_{t}|S\_{t})}{b(A\_{t}|S\_{t})}\frac{\pi(A\_{t+1}|S\_{t+1})}{b(A\_{t+1}|S\_{t+1})}\frac{\pi(A\_{t+2}|S\_{t+2})}{b(A\_{t+2}|S\_{t+2})}....\frac{\pi(A\_{t+k-2}|S\_{t+k-2})}{b(A\_{t+k-2}|S\_{t+k-2})}\frac{\pi(A\_{t+k}|S\_{t+k})}{b(A\_{t+k}|S\_{t+k})}......\frac{\pi(A\_{T-1}|S\_{T-1})}{b(A\_{T-1}|S\_{T-1})}\right]\mathbb{E}\left[\frac{\pi(A\_{t+k-1}|S\_{t+k-1})}{b(A\_{t+k-1}|S\_{t+k-1})}R\_{t+k}\right] \\= \mathbb{E}\left[\frac{\pi(A\_{t}|S\_{t})}{b(A\_{t}|S\_{t})}\right]\mathbb{E}\left[\frac{\pi(A\_{t+1}|S\_{t+1})}{b(A\_{t+1}|S\_{t+1})}\right]\mathbb{E}\left[\frac{\pi(A\_{t+2}|S\_{t+2})}{b(A\_{t+2}|S\_{t+2})}\right]....\mathbb{E}\left[\frac{\pi(A\_{t+k-2}|S\_{t+k-2})}{b(A\_{t+k-2}|S\_{t+k-2})}\right]\mathbb{E}\left[\frac{\pi(A\_{t+k}|S\_{t+k})}{b(A\_{t+k}|S\_{t+k})}\right]......\mathbb{E}\left[\frac{\pi(A\_{T-1}|S\_{T-1})}{b(A\_{T-1}|S\_{T-1})}\right]\mathbb{E}\left[\frac{\pi(A\_{t+k-1}|S\_{t+k-1})}{b(A\_{t+k-1}|S\_{t+k-1})}R\_{t+k}\right] \\= \mathbb{E}[\frac{\pi\_{t+k-1}}{b\_{t+k-1}}R\_{t+k}]\\=\mathbb{E}[\rho\_{t+k-1}R\_{t+k}]$
  
  ### which is not equal to eq 5.14. What's the mistake in the above calculations? Are 1 and 2 correct?
  
  **Tags:** reinforcement-learning, off-policy-methods, expectation, importance-sampling, conditional-probability
  > **Comments:**
  > **username_1**: To answer your last question, in general, the expectation of the product of two random variables is not equal to the product of the expectations of each random variable, unless the random variables are independent. That doesn't seem to be true in your case (given that the policies at successive time steps could be correlated), but I could be wrong (because I know little or almost nothing about importance sampling and related topics).  
  > **username_0**: I don't think policies at successive time steps are correlated, otherwise there would have been no point of giving eq 5.13. Also in theory given in the book, $\pi$ is sometimes taken as epsilon-greedy which is not correlated  
  > **username_2**: You made a mistake in step 2. State $S_{k+1}$ depends on $S_k$ and $A_k$ through conditional probability $p(s'|s,a)$ so you cant do what you did.  
  > **username_0**: $S_{k+1}$ is indeed dependent on $S_k$ but $A_k|S_k $ is independent of $A_{k+1}|S_{k+1}$ because $P(A_k|S_k)$ means, given $S_k = s$, what's the probability of choosing $A_k = a$ , similarly for $P(A_{k+1}|S_{k+1})$ . Hence since we are given $S_{k+1} = s'$, there is no need to calculate $p(s'|s,a)$. Is something wrong in this way of thinking??  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2020-09-11. Score: 0
  
  **First Part**
  
  We can reduce variance in off-policy importance sapling, even in the absence of discounting ($\gamma = 1$). Notice that the off-policy estimators are made up of terms like
  $$\rho\_{t:T-1}G\_t = \rho\_{t:T-1} (R\_{t+1} + \gamma R\_{t+2} + \dots+ \gamma^{T-t-1}R\_{T})$$
  
  and consider the second term, imagine $\gamma$=$1$:
  $$\rho\_{t:T-1}R\_{t+2} = \frac{\pi(A\_t|S\_t) \pi(A\_{t+1}|S\_{t+1})......\pi(A\_{T-1}|S\_{T-1})}{b(A\_t|S\_t) b(A\_{t+1}|S\_{t+1})...... b(A\_{T-1}|S\_{T-1})} R\_{t+2}$$
  In above equation, the term $\pi(A\_t|S\_t)$, $\pi(A\_{t+1}|S\_{t+1})$, $R\_{t+2}$ are correleated, all the other terms are independent of each other.
  
  Notice the very import property of expectation:
  $E[ab] = E[a] E[b]$ if and only if $a$, $b$ are independent random variables.
  
  Now:
  $$ E[\frac{\pi(A\_t|S\_t) \pi(A\_{t+1}|S\_{t+1}).....\pi(A\_{T-1}|S\_{T-1})}{b(A\_t|S\_t) b(A\_{t+1}|S\_{t+1}).....b(A\_{T-1}|S\_{T-1})} R\_{t+2}]$$
  $$ = E[\frac{\pi(A\_t|S\_t) \pi(A\_{t+1}|S\_{t+1})}{b(A\_t|S\_t) b(A\_{t+1}|S\_{t+1})} R\_{t+2}] E[\frac{\pi(A\_{t+2}|S\_{t+2})}{b(A\_{t+2}|S\_{t+2})}] ..... E[\frac{\pi(A\_{T-1}|S\_{T-1})}{b(A\_{T-1}|S\_{T-1})}]$$
  $$ = E[\frac{\pi(A\_t|S\_t) \pi(A\_{t+1}|S\_{t+1})}{b(A\_t|S\_t) b(A\_{t+1}|S\_{t+1})} R\_{t+2}] \sum\_a b(a|s\_{t+2}) \frac{\pi(a|s\_{t+2}}{b(a|s\_{t+2}}.....\sum\_a b(a|s\_{T-1}) \frac{\pi(a|s\_{T-1}}{b(a|s\_{T-1}} $$
  $$ = E[\frac{\pi(A\_t|S\_t) \pi(A\_{t+1}|S\_{t+1})}{b(A\_t|S\_t) b(A\_{t+1}|S\_{t+1})} R\_{t+2}] \sum\_a \pi(a|s\_{t+2}).....\sum\_a \pi(a|s\_{T-1})$$  
  $$ = E[\frac{\pi(A\_t|S\_t) \pi(A\_{t+1}|S\_{t+1})}{b(A\_t|S\_t) b(A\_{t+1}|S\_{t+1})} R\_{t+2}] 1 \* 1 $$
  $$ = E[\frac{\pi(A\_t|S\_t) \pi(A\_{t+1}|S\_{t+1})}{b(A\_t|S\_t) b(A\_{t+1}|S\_{t+1})} R\_{t+2}] $$
  therefore
  $$ E[\rho\_{t:T-1}R\_{t+2}] = E[\rho\_{t:t+1} R\_{t+2}]$$
  If we repeat this analysis for the $k$th term, we will get:
  $$E[\rho\_{t:T-1}R\_{t+k}] = E[\rho\_{t:t+k-1} R\_{t+k}]$$
  It follows that the expectation of our original term can be written:
  $$E[\rho\_{t:T-1}G\_{t}] = E[\tilde{G\_{t}}]$$
  where
  $$\tilde{G}\_t \doteq \rho\_{t:t}R\_{t+1} + \gamma \rho\_{t:t+1}R\_{t+2} + \gamma^{2} \rho\_{t:t+2}R\_{t+3} + ...... + \gamma^{T-t-1} \rho\_{t:T-1}R\_{T}$$
  We call this idea per reward importance sampling. It follows immediately that there is an alternative importance sampling estimate, with the same unbiased expectation as the ordinary importance sampling estimate:
  $$V(s) \doteq \frac{\sum\_{t\in\mathcal{T}(s)} \tilde{G}\_t}{|\mathcal{T}(s)|}$$
  which we might expect to sometimes be of lower variance.
  
  **Second Part**
  
  The reward $R\_{k+1}$ depends on the previous $\pi(a\_1|s\_1)$ up to $\pi(a\_{k-1}|s\_{k-1})$. So, you can't seperate them and treat them as independent variable just you did on the aforementioned example.
  
  
  ---
  
  