Answers.Body: <blockquote>
    <p>There is one thing I don't particularly understand. Why do we need the state-transition probability function when calculating the importance sampling ratio for off-policy prediction?</p>
  </blockquote>
  
  <p>It is not needed for calculation. It must be included in the theory, to compare the correct probability of each trajectory (on-policy vs off-policy). However, the state transition probabilities are then also shown to cancel out exactly, so there is no requirement to <em>know</em> what the values are.</p>
  
  <p>State transition probabilities are irrelevant to probability ratios between identical trajectories where the policy varies but the environment does not. Which is the case for off-policy learning.</p>
  
  <p>This is all explained on the relevant pages of the book, but replicating here for completeness. If your trajectory is from steps <span class="math-container">$m$</span> to <span class="math-container">$n$</span> and called <span class="math-container">$\tau = (s_m, a_m, r_{m+1}, s_{m+1}, a_{m+1}, r_{m+2} . . . r_{n}, s_n)$</span>, then the probability of seeing that trajectory under two different policies <span class="math-container">$\pi(a|s)$</span> and <span class="math-container">$b(a|s)$</span> is:</p>
  
  <p><span class="math-container">$$p(\tau|\pi) = (\prod_{i=m}^{n-1} \pi(a_i|s_i))(\prod_{j=m+1}^{n} p(s_j, 
  r_j|s_{j-1},a_{j-1}))$$</span></p>
  
  <p><span class="math-container">$$p(\tau|b) = (\prod_{i=m}^{n-1} b(a_i|s_i))(\prod_{j=m+1}^{n} p(s_j, r_j|s_{j-1},a_{j-1}))$$</span></p>
  
  <p>You can clearly see that the second product in both cases is the same, and cancels out in the ratio:</p>
  
  <p><span class="math-container">$$\frac{p(\tau|\pi)}{p(\tau|b)} =\frac{\prod_{i=m}^{n-1} \pi(a_i|s_i)}{\prod_{i=m}^{n-1} b(a_i|s_i)}$$</span></p>
  
  <p>So it doesn't matter what <span class="math-container">$p(s', r|s, a)$</span> actually <em>is</em>, just that it exists and is not allowed to change in theory between the on-policy and off-policy cases. Or in other words, that the environment is a consistent MDP.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-16T14:21:46.070Z
Answers.Text: Thank you Neil. You are write, I should have continued reading (although i am going through this chapter already several times)
  
  But concerning the requirement for this being the case (both stp canceling each other out) This is true for stationary MDPs? So for any dynamic environment where this changes over time, the learned policy (assuming it was perfect at the end of training) might degenerate over time?
Answers.UserDisplayName: Manuel Pasieka
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-16T14:26:12.787Z
Answers.Text: @ManuelPasieka: Yes if the MDP changes the values may be incorrect later on (when you try to use the target policy). However, that would also have at least some affects on most learning algorithms. If non-stationarity of the environment is a real concern in a problem you are looking at, then you need to be careful applying most RL techniques.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-16T13:57:49.687Z
Answers.LastActivityDate: 2019-02-25T15:30:36.080Z
Answers.LastEditDate: 2019-02-25T15:30:36.080Z
Answers.UserDisplayName: Neil Slater
Body: <p>I am reading the book titled "<a href="https://drive.google.com/file/d/1opPSz5AZ_kVa1uWOdOiveNiBFiEOHjkG/view" rel="nofollow noreferrer">Reinforcement Learning: An Introduction</a>" (by Sutton and Barto). I am at chapter 5, which is about Monte Carlo methods, but now I am quite confused.</p>
  
  <p>There is one thing I don't particularly understand. Why do we need the state-transition probability function when calculating the importance sampling ratio for off-policy prediction?</p>
  
  <p>I understood that one of the main benefits of MC over Dynamic Programming (DP) is that one does not need to have a model of the state-transition probability for a system. Or is this only the case for on-policy MC?</p>
  
Tags: <reinforcement-learning><on-policy-methods><monte-carlo-methods><importance-sampling><dynamic-programming>
Title: Do we need the transition probability function when calculating the importance sampling ratio?
UserDisplayName: Manuel Pasieka
ThreadText: # Do we need the transition probability function when calculating the importance sampling ratio?
  
  (Asked by: username_0 on 2018-11-16)
  
  I am reading the book titled "[Reinforcement Learning: An Introduction](https://drive.google.com/file/d/1opPSz5AZ_kVa1uWOdOiveNiBFiEOHjkG/view)" (by Sutton and Barto). I am at chapter 5, which is about Monte Carlo methods, but now I am quite confused.
  
  There is one thing I don't particularly understand. Why do we need the state-transition probability function when calculating the importance sampling ratio for off-policy prediction?
  
  I understood that one of the main benefits of MC over Dynamic Programming (DP) is that one does not need to have a model of the state-transition probability for a system. Or is this only the case for on-policy MC?
  
  **Tags:** reinforcement-learning, on-policy-methods, monte-carlo-methods, importance-sampling, dynamic-programming
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-11-16. Score: 3 | Accepted answer
  
  > There is one thing I don't particularly understand. Why do we need the state-transition probability function when calculating the importance sampling ratio for off-policy prediction?
  
  It is not needed for calculation. It must be included in the theory, to compare the correct probability of each trajectory (on-policy vs off-policy). However, the state transition probabilities are then also shown to cancel out exactly, so there is no requirement to *know* what the values are.
  
  State transition probabilities are irrelevant to probability ratios between identical trajectories where the policy varies but the environment does not. Which is the case for off-policy learning.
  
  This is all explained on the relevant pages of the book, but replicating here for completeness. If your trajectory is from steps $m$ to $n$ and called $\tau = (s\_m, a\_m, r\_{m+1}, s\_{m+1}, a\_{m+1}, r\_{m+2} . . . r\_{n}, s\_n)$, then the probability of seeing that trajectory under two different policies $\pi(a|s)$ and $b(a|s)$ is:
  
  $$p(\tau|\pi) = (\prod\_{i=m}^{n-1} \pi(a\_i|s\_i))(\prod\_{j=m+1}^{n} p(s\_j,
  r\_j|s\_{j-1},a\_{j-1}))$$
  
  $$p(\tau|b) = (\prod\_{i=m}^{n-1} b(a\_i|s\_i))(\prod\_{j=m+1}^{n} p(s\_j, r\_j|s\_{j-1},a\_{j-1}))$$
  
  You can clearly see that the second product in both cases is the same, and cancels out in the ratio:
  
  $$\frac{p(\tau|\pi)}{p(\tau|b)} =\frac{\prod\_{i=m}^{n-1} \pi(a\_i|s\_i)}{\prod\_{i=m}^{n-1} b(a\_i|s\_i)}$$
  
  So it doesn't matter what $p(s', r|s, a)$ actually *is*, just that it exists and is not allowed to change in theory between the on-policy and off-policy cases. Or in other words, that the environment is a consistent MDP.
  
  > **Comments:**
  > **username_0**: Thank you Neil. You are write, I should have continued reading (although i am going through this chapter already several times)  But concerning the requirement for this being the case (both stp canceling each other out) This is true for stationary MDPs? So for any dynamic environment where this changes over time, the learned policy (assuming it was perfect at the end of training) might degenerate over time?  
  > **username_1**: @ManuelPasieka: Yes if the MDP changes the values may be incorrect later on (when you try to use the target policy). However, that would also have at least some affects on most learning algorithms. If non-stationarity of the environment is a real concern in a problem you are looking at, then you need to be careful applying most RL techniques.  
  
  ---
  
  