Understanding the "unroling" step in the proof of the policy gradient theorem In the proof of the policy gradient theorem in the RL book of Sutton and Barto (that I shamelessly paste here):

there is the &quot;unrolling&quot; 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 &quot;unrolling&quot;?
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 state of transitioning from state $s$ to $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)$.