Answers.Body: <p>It looks like &quot;v of s prime&quot; is just substituted with the already derived value for &quot;v of s&quot;. You can call it a recursion of a kind.
  In other words, v(s) is dependent on v(s') and that implies that v(s') is dependent on v(s''). So we can combine that and get the dependency of v(s) of v(s'').</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-23T08:51:28.710Z
Answers.Text: Where exactly does $Pr(s\rightarrow x, k, \pi)$ come from?
Answers.UserDisplayName: tmaric
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-23T08:52:59.997Z
Answers.Text: This is in the right direction for the first unrolling line, but actually the substituted term is $\nabla v_\pi(s')$ - you can use LaTex to put that into the answer - i.e. `$\nabla v_\pi(s')$`
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-23T09:05:03.987Z
Answers.Text: I see where the unrolling leads, in terms of simply recursively expanding the expression. What I don't see, is how $Pr$ is substituted in the unrolled expression.
Answers.UserDisplayName: tmaric
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-23T08:50:18.937Z
Answers.LastActivityDate: 2020-06-23T08:50:18.937Z
Answers.UserDisplayName: oleg.mosalov
Answers.Body: <p>The unrolling step is due to the fact you end up with an equation that you can keep expanding indefinitely.</p>
  <p>Note that we start with calculating <span class="math-container">$\nabla v_\pi(s)$</span> and arrive at
  <span class="math-container">$$\nabla v_\pi(s) = \sum_a\left[ \nabla \pi(a|s) q_\pi(s,a) + \pi(a|s) \sum_{s'}p(s'|s,a) \nabla v_\pi (s') \right]\;,$$</span>
  which contains a term for <span class="math-container">$\nabla v_\pi(s')$</span>. This is a recursive relationship, similar to the bellman equation, so we can substitute in a term for <span class="math-container">$\nabla v_\pi(s')$</span> which will be a term similar just with <span class="math-container">$\nabla v_\pi(s'')$</span>. As I mentioned, we can do this indefinitely which leads us to</p>
  <p><span class="math-container">$$\nabla v_\pi(s) = \sum_{x \in \mathcal{S}} \sum_{k=0}^\infty \mathbb{P}(s\rightarrow x, k, \pi) \sum_a \nabla \pi(a|x) q_\pi(x,a)\;.$$</span></p>
  <p>We need the term <span class="math-container">$\sum_{x \in \mathcal{S}} \sum_{k=0}^\infty \mathbb{P}(s\rightarrow x, k, \pi)$</span> because we want to take an average over the state space, however due to unrolling there are many different <span class="math-container">$s_t$</span>'s that we need to average over (this comes from the <span class="math-container">$s',s'',s''',...$</span> in the unrolling) so we also need to add the probability of transitioning from state <span class="math-container">$s$</span> to state <span class="math-container">$x$</span> in <span class="math-container">$k$</span> time steps, where we sum over an infinite horizon due to the repeated unrolling.</p>
  <p>If you are wondering what happens to the terms <span class="math-container">$\pi(a|s)$</span> and <span class="math-container">$p(s'|s,a)$</span> terms and why they are not explicitly shown in this final form, it is because this is exactly what the <span class="math-container">$\mathbb{P}(s\rightarrow x, k, \pi)$</span> represents. The average over all possible states accounts for the <span class="math-container">$p(s'|s,a)$</span> and the fact that we follow policy <span class="math-container">$\pi$</span> in the probability statement accounts for the <span class="math-container">$\pi(a|s)$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-23T10:23:18.860Z
Answers.LastActivityDate: 2023-01-08T18:00:25.467Z
Answers.LastEditDate: 2023-01-08T18:00:25.467Z
Answers.UserDisplayName: David
Body: <p>In the proof of the policy gradient theorem in the <a href="http://incompleteideas.net/book/RLbook2020.pdf" rel="nofollow noreferrer">RL book of Sutton and Barto</a> (that I shamelessly paste here):</p>
  <p><a href="https://i.sstatic.net/ASU0q.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ASU0q.png" alt="enter image description here" /></a></p>
  <p>there is the &quot;unrolling&quot; step that is supposed to be immediately clear</p>
  <blockquote>
  <p>With just elementary calculus and re-arranging of terms</p>
  </blockquote>
  <p>Well, it's not. :) Can someone explain this step in more detail?</p>
  <p>How exactly is <span class="math-container">$Pr(s \rightarrow x, k, \pi)$</span> deduced by &quot;unrolling&quot;?</p>
  
Tags: <reinforcement-learning><policy-gradients><proofs><sutton-barto><policy-gradient-theorem>
Title: How exactly is $Pr(s \rightarrow x, k, \pi)$ deduced by "unrolling", in the proof of the policy gradient theorem?
UserDisplayName: tmaric
ThreadText: # How exactly is $Pr(s \rightarrow x, k, \pi)$ deduced by "unrolling", in the proof of the policy gradient theorem?
  
  (Asked by: username_0 on 2020-06-23)
  
  In the proof of the policy gradient theorem in the [RL book of Sutton and Barto](http://incompleteideas.net/book/RLbook2020.pdf) (that I shamelessly paste here):
  
  [![enter image description here](https://i.sstatic.net/ASU0q.png)](https://i.sstatic.net/ASU0q.png)
  
  there is the "unrolling" step that is supposed to be immediately clear
  
  > With just elementary calculus and re-arranging of terms
  
  Well, it's not. :) Can someone explain this step in more detail?
  
  How exactly is $Pr(s \rightarrow x, k, \pi)$ deduced by "unrolling"?
  
  **Tags:** reinforcement-learning, policy-gradients, proofs, sutton-barto, policy-gradient-theorem
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2020-07-23. Score: 3 | Accepted answer
  
  The unrolling step is due to the fact you end up with an equation that you can keep expanding indefinitely.
  
  Note that we start with calculating $\nabla v\_\pi(s)$ and arrive at
  $$\nabla v\_\pi(s) = \sum\_a\left[ \nabla \pi(a|s) q\_\pi(s,a) + \pi(a|s) \sum\_{s'}p(s'|s,a) \nabla v\_\pi (s') \right]\;,$$
  which contains a term for $\nabla v\_\pi(s')$. This is a recursive relationship, similar to the bellman equation, so we can substitute in a term for $\nabla v\_\pi(s')$ which will be a term similar just with $\nabla v\_\pi(s'')$. As I mentioned, we can do this indefinitely which leads us to
  
  $$\nabla v\_\pi(s) = \sum\_{x \in \mathcal{S}} \sum\_{k=0}^\infty \mathbb{P}(s\rightarrow x, k, \pi) \sum\_a \nabla \pi(a|x) q\_\pi(x,a)\;.$$
  
  We need the term $\sum\_{x \in \mathcal{S}} \sum\_{k=0}^\infty \mathbb{P}(s\rightarrow x, k, \pi)$ because we want to take an average over the state space, however due to unrolling there are many different $s\_t$'s that we need to average over (this comes from the $s',s'',s''',...$ in the unrolling) so we also need to add the probability of transitioning from state $s$ to state $x$ in $k$ time steps, where we sum over an infinite horizon due to the repeated unrolling.
  
  If you are wondering what happens to the terms $\pi(a|s)$ and $p(s'|s,a)$ terms and why they are not explicitly shown in this final form, it is because this is exactly what the $\mathbb{P}(s\rightarrow x, k, \pi)$ represents. The average over all possible states accounts for the $p(s'|s,a)$ and the fact that we follow policy $\pi$ in the probability statement accounts for the $\pi(a|s)$.
  
  
  ---
  
  ### Answer by username_1 on 2020-06-23. Score: -1
  
  It looks like "v of s prime" is just substituted with the already derived value for "v of s". You can call it a recursion of a kind.
  In other words, v(s) is dependent on v(s') and that implies that v(s') is dependent on v(s''). So we can combine that and get the dependency of v(s) of v(s'').
  
  > **Comments:**
  > **username_0**: Where exactly does $Pr(s\rightarrow x, k, \pi)$ come from?  
  > **username_2**: This is in the right direction for the first unrolling line, but actually the substituted term is $\nabla v_\pi(s')$ - you can use LaTex to put that into the answer - i.e. `$\nabla v_\pi(s')$`  
  > **username_0**: I see where the unrolling leads, in terms of simply recursively expanding the expression. What I don't see, is how $Pr$ is substituted in the unrolled expression.  
  
  ---
  
  