How to simplify policy gradient theorem to $E_{\pi}[G_t \frac{\nabla_{\theta}\pi(a|S_t,\theta)}{\pi(a|S_t,\theta)}]$?

Question

In "Introduction to Reinforcement Learning" (Richard Sutton) section 13.3(Reinforce algorithm) they have the following equation:

\begin{align} \nabla_{\theta}J &\propto \sum_s \mu(s) \sum_a q_{\pi}(s,a)\nabla_{\theta}\pi(a|s,\theta) \\ &= E_{\pi}[\sum_a q_{\pi}(S_t,a) \nabla_{\theta}\pi(a|S_t,\theta)] \tag{1}\label{1} \end{align} But in my opinion equation 1 should be expectation over state distribution: $$E_{\mu}[\sum_a q_{\pi}(S_t,a) \nabla_{\theta}\pi(a|S_t,\theta)]$$ If I am right here then the rest of the lines follows like this: \begin{align} \nabla_{\theta}J &= E_{\mu}[\sum_a q_{\pi}(S_t,a) \nabla_{\theta}\pi(a|S_t,\theta)] \\ &= E_{\mu}[\sum_a \pi(a|S_t,\theta) q_{\pi}(S_t,a) \frac{\nabla_{\theta}\pi(a|S_t,\theta)}{\pi(a|S_t,\theta)}] \\ &= E_{\mu}[E_{\pi}[q_{\pi}(S_t,A_t)\frac{\nabla_{\theta}\pi(A_t|S_t,\theta)}{\pi(A_t|s,\theta)}]]\\ &= E_{\mu}[E_{\pi}[G_t\frac{\nabla_{\theta}\pi(a|S_t,\theta)}{\pi(a|S_t,\theta)}]] \end{align} Now the final update rule using stochastic gradient descent will be: $$\triangle \theta = \alpha E_{\pi}[G_t\frac{\nabla_{\theta}\pi(A_t|S_t,\theta)}{\pi(A_t|S_t,\theta)}] \tag{2}$$ I think I am doing something wrong here because this equation 2 does not match with the book also with other materials. Can anyone please show me where I am doing wrong?

Answer 1

When the authors write go from $$\nabla_{\theta}J \propto \sum_s \mu(s) \sum_a q_{\pi}(s,a)\nabla_{\theta}\pi(a|s;\theta)\;$$ to $$\nabla_{\theta}J = E_{\pi}\left[\sum_a q_{\pi}(S_t,a) \nabla_{\theta}\pi(a|S_t;\theta)\right]\;$$ they are simply taking an expectation where the only random variable is the state $S_t$. This is because, as they say in the book, the Policy Gradient Theorem is a sum over a state distribution, therefore it can be written as an expectation. The expectation is over the states wrt the state distribution; the $\pi$ subscript here does not mean we are taking expectation with respect to the action policy $\pi$, they use the notation $\pi$ to emphasise that the state distribution is induced by the current policy $\pi$ -- this is what makes REINFORCE an on-policy algorithm because the state distribution with which we take the expectation must come from the current policy $\pi$, not some arbitrary distribution.

Now, as you don't seem to understand how they go from this to the Stochastic Gradient Ascent (SGA) (NOT descent as you keep referring to it as) update rule in the book, I will explain further. As you rightly say we can go from my previous equation to the following $$\nabla_{\theta}J = E_{\pi}\left[G_t \nabla_{\theta}\log\pi(A_t|S_t;\theta)\right]\;$$ by doing some re-arranging and noting that $G_t$ is an unbiased estimate of $q_\pi(s, a)$ when taking expectation over the actions and states. Now, this expectation we have is with respect to the actions and states; your first mistake is that you have made it an expectation over the actions without signifying that the action is now a random variable (maybe you could look up expectations and random variables to understand really what this means).

Your second mistake is by not seeing how you can use this gradient to optimise the policy parameters. As we want to maximise this objective we want to perform SGA to it; that is we want to perform $$\theta = \theta + \alpha \nabla_\theta J\;;$$ but $\nabla_\theta J$ is an expectation. It would be costly to evaluate this at every single state-action pair that we see in an episode, thus we only perform SGA for one state-action tuple at a time. Now, you might think that this is not correct, but it is in fact an unbiased estimate as we will sample lots of state-action pairs; this kind of estimation is known as Monte Carlo Sampling. Therefore, we can write our REINFORCE update rule as

$$\theta = \theta + \alpha G_t \nabla_\theta \log \pi(A_t | S_t; \theta)\;;$$

which is exactly the update rule in the book.

Note that at the start of the chapter in Sutton and Barto they also make it clear that we wish to perform $$\theta = \theta + \alpha \hat{\nabla J(\theta)} \;;$$ where $\hat{\nabla J(\theta)}$ is a stochastic estimate whose expectation approximates the true gradient; this is exactly what we are doing, $G_t \nabla_\theta \log \pi(A_t | S_t; \theta)$ is our stochastic estimate.