# 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