3
$\begingroup$

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

enter image description 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"?

$\endgroup$

2 Answers 2

3
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .