# What is the difference between Sutton's and Levine's REINFORCE algorithm?

I followed the videos/slides of Berkley RL course, but now I am a bit confused when implementing it. Please see the picture below.

In particular, what does $$i$$ represent in the REINFORCE algorithm? If $$\tau^i$$ is the trajectory for the whole episode $$i$$, then why don't we average across the episodes $$\frac{1}{N}$$, which approximates the gradient of the objective function? Instead, it is a sum over the $$i$$. So, do we update the gradients per episode or have batches of episodes to update it? When I compare the algorithm to Sutton's book as shown below, I see that there we update the gradients per episode.

But wouldn't it then contradict the derivation on the Levine's slide that the gradient of the objective function $$J$$ is the expectation (therefore sampling) of the gradients of the logs?

Secondly, why do we have a cumulative sum of the returns over $$T$$ in Sutton's version but do not do it in Levine's (instead, all returns are summed together)

About the first question, you are right. The $$i$$ denotes a sample trajectory corresponding to a whole episode. However, Sutton's version is exactly the same one as Levine's if you choose $$N=1$$.
About the second question, the Policy Gradient theorem only tells you what is the gradient up to a constant, so basically any constant is irrelevant. Now, even if you do know the constant, you are going to multiply the gradients by an arbitrary learning rate $$\alpha$$. So, you can think that the factor $$\frac{1}{N}$$ is actually already considered "inside" $$\alpha$$.
• The PG theorem tells you that the gradient $\nabla J$ is proportional to the expected value of $G\sum_t\nabla\log\pi(a_t|s_t)$. So, your actual gradient is $C\mathbb E\left[G\sum_t\nabla\log\pi(a_t|s_t)\right]$, where $C$ is some constant. If you perform an SGD step with learning rate $\eta$, then your new parameters will be $\theta\leftarrow\theta+\eta\nabla J \approx\theta+\frac{C\eta}{N}\sum_iG_i\sum_t\nabla\log\pi(a_t^i|s_t^i)$. If you define $\alpha=\frac{C\eta}{N}$, you will obtain Levine's version. Since $\eta$ is arbitrary, you can see that $C$ or $\frac{1}{N}$ are irrelevant. Jan 8, 2020 at 22:23
• So, to answer your question, the fact that we usually don't know $C$ and that the learning rate $\eta$ is arbitrary makes irrelevant if you decide to consider the sum or the mean over the trajectories, that is, both are valid approximations of your gradient. Jan 8, 2020 at 22:27
The answer of your question can be explain like this, both of these fomulars are using the estimation of the expectation $$\mathbb E[G\sum_{t}\nabla log \pi(a_t|s_t)]$$. The difference is that the Sutton's version use only one sample of the trajectory distribution while the Levine's version use many trajectories. This can cause the difference in the parameters $$\theta$$ after training. However, this difference is neglectable, and the value of the parameters of two versions are close to each other $$\theta_1 \approx \theta_2$$. To explain, suppose that the learning rate is chosen very small so that $$\mathbb \alpha E[ G\sum_{t}\nabla log \pi(a_t|s_t)]=E[\alpha G\sum_{t}\nabla log \pi(a_t|s_t)]\approx\alpha G\sum_{t}\nabla log \pi(a_t|s_t)$$ or the gradient of the Sutton's version oscillate around the Levine's version with a small variance.