# 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. Commented 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. Commented Jan 8, 2020 at 22:27