Deriving REINFORCE algorithm from policy gradient theorem for the episodic case

Question

In the draft for Sutton's latest RL book, page 270, he derives the REINFORCE algorithm from the policy gradient theorem. The first part is the equivalence

$$\sum_{s}d_\pi(s)\sum_{a}{q_\pi(s,a)\nabla\pi (a|s,\theta)} = \mathbf{E}[\gamma^t\sum_{a}{q_\pi(S_t,a)\nabla\pi (a|S_t,\theta)}] $$

where $$d_\pi(s) = \sum_{k=0}^{\infty}{\gamma^kP(S_k = s | S_0, \pi)}$$

This makes intuitive sense (we just sample our trajectory, and we expect that we will average the long term trajectory), but I'm having trouble deriving this analytically. The discount factor $\gamma^t$ stops us from treating $d_\pi$ as simply a probability distribution, so we aren't just taking the expected value over the states. Can anyone point me in the right direction please?

Answer 1

The expectation is over states we sample when running the policy. Suppose $D$ is the multiset containing all the states we've visited in our dataset, and $D_t$ is the same thing, but only containing those states visited at exactly time $t$: $$\nabla \eta(\theta) = E_{\pi}\left[\gamma^t \sum_a q_{\pi}(S_t, a) \nabla_{\theta} \pi(a|S_t,\theta)\right] $$ Then we can write this as an expectation over the distribution of possible multisets D. (Let the size of D be $n$) $$= E\left[ \frac{1}{n} \sum_{s \in D} \gamma^t \sum_a q_{\pi}(S_t, a) \nabla_{\theta} \pi(a|S_t,\theta) \right] \\ = \sum_t E\left [ \frac{1}{n} \sum_{s \in D_t} \gamma^t \sum_a q_{\pi}(S_t, a) \nabla_{\theta} \pi(a|S_t,\theta) \right] \\ = \sum_t \sum_{s \in S} \frac{1}{n} P(s \in D_t) \gamma^t \sum_a q_{\pi}(S_t, a) \nabla_{\theta} \pi(a|S_t,\theta) \\ = \sum_t \sum_{s \in S} P(S_t = s | S_0, \pi) \gamma^t \sum_a q_{\pi}(S_t, a) \nabla_{\theta} \pi(a|S_t,\theta) $$ Then reorder the sums $$= \sum_{s \in S} \sum_t P(S_t = s | S_0, \pi) \gamma^t \sum_a q_{\pi}(S_t, a) \nabla_{\theta} \pi(a|S_t,\theta) \\ = \sum_{s \in S} d_{\pi}(s) \sum_a q_{\pi}(S_t, a) \nabla_{\theta} \pi(a|S_t,\theta) $$ Which is the result we want.

Answer 2

As a remark:

There are some different variations of the REINFORCE formula in different sources.

Sutton & Barto end up deriving the formula:

$ \frac{\partial}{\partial \theta}v(S_0;\theta)=\sum_{t=0}^{T-1}\gamma^tG_t \frac{\partial}{\partial \theta} \ln \pi(A_t|S_t;\theta) $

Another variation of the formula are given in http://www.scholarpedia.org/article/Policy_gradient_methods

Here the formula derived are;

$ \frac{\partial}{\partial \theta}v(S_0;\theta)= G_0 \sum_{t=0}^{T-1} \frac{\partial}{\partial \theta} \ln \pi(A_t|S_t;\theta) $

As far as I can tell the reason for the deviation are a fault in Sutton & Barto. One step in their derivation assume that $ \frac{\partial}{\partial \theta}r(s',s,a)=0 $. However $ \theta $ affect the policy, which affect $ a $ and $ s' $. As a result, the reward $ r $ are not invariant under changes in $ \theta $.

Answer 3

@flush_bingo you can get $\frac{\partial r(s',s,a)}{\partial \theta_1} = 0$ by considering the classical definition of partial derivative i.e. for a given tuple of $(s',s, a)$

$$\frac{\partial r(s',s,a)}{\partial \theta_1} = \frac{r(s',s,a)_{\theta_1+\Delta\theta_1} - r(s',s,a)_{\theta_1}}{\Delta\theta_1}$$

Since the value of reward for taking a action $a$ in state $s$ and getting to state $s'$ is going to be the same no matter what the value of $\theta_1$ is the partial derivative is zero. Different values of $\theta_1$ are only going to affect the frequency with which $r(s',s,a)$ appears.

You can follow the same logic for the derivative of transition model with respect to policy parameters i.e.

$$\frac{\partial P(s'|s,a)}{\partial \theta_1} = 0$$