Answers.Body: <p>It has nothing to do with Bayes rule, like you said, <span class="math-container">$G_t$</span> is the return we get by following the policy <span class="math-container">$b$</span> , so the value of the state we get that return in is equal to the expected value of that return. On page 59 of the book, equation 3.14 derives the value of the state as expected value of the return but in this case we are following the behaviour policy <span class="math-container">$b$</span> so you would replace <span class="math-container">$\pi (a \mid s)$</span> with <span class="math-container">$b (a \mid s)$</span> and <span class="math-container">$v_\pi (s')$</span> with <span class="math-container">$v_b (s')$</span> and you would get the value of the state following the policy <span class="math-container">$b$</span>, that is <span class="math-container">$v_b (s)$</span>.<br>
  We are actually interested in the value of the state when we follow target policy <span class="math-container">$\pi$</span> , but we got the value by following behaviour policy, so we will multiply that expression with importance sampling ratio. If we do that <span class="math-container">$b (a \mid s)$</span> terms will cancel out and you are only left with term <span class="math-container">$\pi (a \mid s)$</span> from importance sampling ratio so we will get the value by following the target policy <span class="math-container">$\pi$</span> that is <span class="math-container">$v_\pi (s)$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-19T16:44:39.837Z
Answers.Text: That was clear explanation. But, could you show how the terms cancel?
Answers.UserDisplayName: Zach Zhao
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-19T20:22:34.843Z
Answers.Text: importance sampling ratio for state $s$ is $\pi (a \mid s) / b (a \mid s)$ and $b (a \mid s)$ term in that ratio will cancel out with term $b (a \mid s)$ from first sum in expression 3.14 (the modified one as I described above). Notice that expression 3.14 is recursive so same would apply for value $v_b (s')$ which you would write out the same way as $v_b (s)$ is written out in 3.14, but in that state (state $s'$ ) importance sampling ratio would be $\pi (a \mid s') / b (a \mid s')$ and now terms $b (a \mid s')$ would cancel out and so on, you would keep writing out next states until the end
Answers.UserDisplayName: Brale
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-20T17:02:48.883Z
Answers.Text: I see how the value terms could recursively cancel out with the sampling ratio, but would the reward terms be affected unequally when expanding?
Answers.UserDisplayName: Zach Zhao
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-20T19:28:28.257Z
Answers.Text: sorry, I think I expressed myself incorrectly. You wouldn't actually calculate expected value and then multiply it with importance sampling ratio (notice how ratio is "inside" the expectation term that is shown in the picture you posted), you would consider importance sampling ratio while calculating expected value, so terms of total importance sampling ratio would "distribute" themselves across the states and then terms would cancel out like I described in previous comment so rewards wouldn't be affected by multiple policy probabilities (if that is what you meant), hopefully this is clear now
Answers.UserDisplayName: Brale
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-19T10:31:25.260Z
Answers.LastActivityDate: 2018-12-19T10:31:25.260Z
Answers.UserDisplayName: Brale
Answers.Body: <p><span class="math-container">$\mathbb{E}_{X\thicksim P}[f(X)] = \sum P(X)f(X) = \sum Q(X)\frac{P(X)}{Q(X)}f(X) = \mathbb{E}_{X\thicksim Q}\left[\frac{P(X)}{Q(X)}f(X)\right]$</span></p>
  
  <p>Here <span class="math-container">$P = \pi, Q = b ,f = G_t|S_t $</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-13T21:11:25.243Z
Answers.LastActivityDate: 2020-06-13T21:11:25.243Z
Answers.UserDisplayName: ZERO NULLS
Body: <p>When reading the book by Sutton and Barto, I came across the <em>importance sampling ratio</em>.</p>
  
  <p>The first equation, I believe, describes the probability a particular sequence is obtained given the current state, and the policy.</p>
  
  <p><span class="math-container">\begin{align}
  &amp;\operatorname{Pr}\left\{A_{t}, S_{t+1}, A_{t+1}, \ldots, S_{T} | S_{t}, A_{t: T-1} \sim \pi\right\} \\
  &amp;=\pi\left(A_{t} | S_{t}\right) p\left(S_{t+1} | S_{t}, A_{t}\right) \pi\left(A_{t+1} | S_{t+1}\right) \cdots p\left(S_{T} | S_{T-1}, A_{T-1}\right) \\
  &amp;=\prod_{k=t}^{T-1} \pi\left(A_{k} | S_{k}\right) p\left(S_{k+1} | S_{k}, A_{k}\right)
  \end{align}</span></p>
  
  <p>The next part takes the ratio between the probabilities of the two trajectories:</p>
  
  <p><span class="math-container">$$\rho_{t: T-1} \doteq \frac{\prod_{k=t}^{T-1} \pi\left(A_{k} | S_{k}\right) p\left(S_{k+1} | S_{k}, A_{k}\right)}{\prod_{k=t}^{T-1} b\left(A_{k} | S_{k}\right) p\left(S_{k+1} | S_{k}, A_{k}\right)}=\prod_{k=t}^{T-1} \frac{\pi\left(A_{k} | S_{k}\right)}{b\left(A_{k} | S_{k}\right)}$$</span></p>
  
  <p>I don't understand how this ratio could lead to this:</p>
  
  <p><span class="math-container">$$\mathbb{E}\left[\rho_{t: T-1} G_{t} | S_{t}=s\right]=v_{\pi}(s)$$</span></p>
  
  <p>The <span class="math-container">$G_t$</span> rewards are obtained through the <span class="math-container">$b$</span> policy, not the <span class="math-container">$\pi$</span> policy.</p>
  
  <p>I think there is something to do with Bayes rule, but I could not derive it. Could someone guide me through the derivation?</p>
  
Tags: <reinforcement-learning><math><markov-decision-process><importance-sampling>
Title: In the context of importance sampling ratio, how is the equation $\mathbb{E}\left[\rho_{t: T-1} G_{t} | S_{t}=s\right]=v_{\pi}(s)$ derived?
UserDisplayName: Zach Zhao
ThreadText: # In the context of importance sampling ratio, how is the equation $\mathbb{E}\left[\rho_{t: T-1} G_{t} | S_{t}=s\right]=v_{\pi}(s)$ derived?
  
  (Asked by: username_0 on 2018-12-17)
  
  When reading the book by Sutton and Barto, I came across the *importance sampling ratio*.
  
  The first equation, I believe, describes the probability a particular sequence is obtained given the current state, and the policy.
  
  \begin{align}
  &\operatorname{Pr}\left\{A\_{t}, S\_{t+1}, A\_{t+1}, \ldots, S\_{T} | S\_{t}, A\_{t: T-1} \sim \pi\right\} \\
  &=\pi\left(A\_{t} | S\_{t}\right) p\left(S\_{t+1} | S\_{t}, A\_{t}\right) \pi\left(A\_{t+1} | S\_{t+1}\right) \cdots p\left(S\_{T} | S\_{T-1}, A\_{T-1}\right) \\
  &=\prod\_{k=t}^{T-1} \pi\left(A\_{k} | S\_{k}\right) p\left(S\_{k+1} | S\_{k}, A\_{k}\right)
  \end{align}
  
  The next part takes the ratio between the probabilities of the two trajectories:
  
  $$\rho\_{t: T-1} \doteq \frac{\prod\_{k=t}^{T-1} \pi\left(A\_{k} | S\_{k}\right) p\left(S\_{k+1} | S\_{k}, A\_{k}\right)}{\prod\_{k=t}^{T-1} b\left(A\_{k} | S\_{k}\right) p\left(S\_{k+1} | S\_{k}, A\_{k}\right)}=\prod\_{k=t}^{T-1} \frac{\pi\left(A\_{k} | S\_{k}\right)}{b\left(A\_{k} | S\_{k}\right)}$$
  
  I don't understand how this ratio could lead to this:
  
  $$\mathbb{E}\left[\rho\_{t: T-1} G\_{t} | S\_{t}=s\right]=v\_{\pi}(s)$$
  
  The $G\_t$ rewards are obtained through the $b$ policy, not the $\pi$ policy.
  
  I think there is something to do with Bayes rule, but I could not derive it. Could someone guide me through the derivation?
  
  **Tags:** reinforcement-learning, math, markov-decision-process, importance-sampling
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2018-12-19. Score: 0 | Accepted answer
  
  It has nothing to do with Bayes rule, like you said, $G\_t$ is the return we get by following the policy $b$ , so the value of the state we get that return in is equal to the expected value of that return. On page 59 of the book, equation 3.14 derives the value of the state as expected value of the return but in this case we are following the behaviour policy $b$ so you would replace $\pi (a \mid s)$ with $b (a \mid s)$ and $v\_\pi (s')$ with $v\_b (s')$ and you would get the value of the state following the policy $b$, that is $v\_b (s)$.  
  We are actually interested in the value of the state when we follow target policy $\pi$ , but we got the value by following behaviour policy, so we will multiply that expression with importance sampling ratio. If we do that $b (a \mid s)$ terms will cancel out and you are only left with term $\pi (a \mid s)$ from importance sampling ratio so we will get the value by following the target policy $\pi$ that is $v\_\pi (s)$
  
  > **Comments:**
  > **username_0**: That was clear explanation. But, could you show how the terms cancel?  
  > **username_1**: importance sampling ratio for state $s$ is $\pi (a \mid s) / b (a \mid s)$ and $b (a \mid s)$ term in that ratio will cancel out with term $b (a \mid s)$ from first sum in expression 3.14 (the modified one as I described above). Notice that expression 3.14 is recursive so same would apply for value $v_b (s')$ which you would write out the same way as $v_b (s)$ is written out in 3.14, but in that state (state $s'$ ) importance sampling ratio would be $\pi (a \mid s') / b (a \mid s')$ and now terms $b (a \mid s')$ would cancel out and so on, you would keep writing out next states until the end  
  > **username_0**: I see how the value terms could recursively cancel out with the sampling ratio, but would the reward terms be affected unequally when expanding?  
  > **username_1**: sorry, I think I expressed myself incorrectly. You wouldn't actually calculate expected value and then multiply it with importance sampling ratio (notice how ratio is "inside" the expectation term that is shown in the picture you posted), you would consider importance sampling ratio while calculating expected value, so terms of total importance sampling ratio would "distribute" themselves across the states and then terms would cancel out like I described in previous comment so rewards wouldn't be affected by multiple policy probabilities (if that is what you meant), hopefully this is clear now  
  
  ---
  
  ### Answer by username_2 on 2020-06-13. Score: 0
  
  $\mathbb{E}\_{X\thicksim P}[f(X)] = \sum P(X)f(X) = \sum Q(X)\frac{P(X)}{Q(X)}f(X) = \mathbb{E}\_{X\thicksim Q}\left[\frac{P(X)}{Q(X)}f(X)\right]$
  
  Here $P = \pi, Q = b ,f = G\_t|S\_t $
  
  
  ---
  
  