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 "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"?

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)$$.

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'').

• Where exactly does $Pr(s\rightarrow x, k, \pi)$ come from? Jun 23 '20 at 8:51
• 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')$ Jun 23 '20 at 8:52
• 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. Jun 23 '20 at 9:05