Why does the discount rate in the REINFORCE algorithm appear twice?

Question

I was reading the book Reinforcement Learning: An Introduction by Richard S. Sutton and Andrew G. Barto (complete draft, November 5, 2017).

On page 271, the pseudo-code for the episodic Monte-Carlo Policy-Gradient Method is presented. Looking at this pseudo-code I can't understand why it seems that the discount rate appears 2 times, once in the update state and a second time inside the return. [See the figure below]

It seems that the return for the steps after step 1 are just a truncation of the return of the first step. Also, if you look just one page above in the book you find an equation with just 1 discount rate (the one inside the return.)

Why then does the pseudo-code seem to be different? My guess is that I am misunderstanding something:

$$ {\mathbf{\theta}}_{t+1} ~\dot{=}~\mathbf{\theta}_t + \alpha G_t \frac{{\nabla}_{\mathbf{\theta}} \pi \left(A_t \middle| S_t, \mathbf{\theta}_{t} \right)}{\pi \left(A_t \middle| S_t, \mathbf{\theta}_{t} \right)}. \tag{13.6} $$

Answer 1

The discount factor does appear twice, and this is correct.

This is because the function you are trying to maximise in REINFORCE for an episodic problem (by taking the gradient) is the expected return from a given (distribution of) start state:

$$J(\theta) = \mathbb{E}_{\pi(\theta)}[G_t|S_t = s_0, t=0]$$

Therefore, during the episode, when you sample the returns $G_1$, $G_2$ etc, these will be less relevant to the problem you are solving, reduced by the discount factor a second time as you noted. At the extreme with an episodic problem and $\gamma = 0$ then REINFORCE will only find an optimal policy for the first action.

In continuing problems, you would use different formulations for $J(\theta)$, and these do not lead to the extra factor of $\gamma^t$.

Answer 2

Neil's answer already provides some intuition as to why the pseudocode (with the extra $\gamma^t$ term) is correct.

I'd just like to additionally clarify that you do not seem to be misunderstanding anything, Equation (13.6) in the book is indeed different from the pseudocode.

Now, I don't have the edition of the book that you mentioned right here, but I do have a later draft from March 22, 2018, and the text on this particular topic seems to be similar. In this edition:

• Near the end of page 326, it is explicitly mentioned that they'll assume $\gamma = 1$ in their proof for the Policy Gradient Theorem.
• That proof eventually leads to the same Equation (13.6) on page 329.
• Immediately below the pseudocode, on page 330, they actually briefly address the difference between the Equation and the pseudocode, saying that that difference is due to the assumption of $\gamma = 1$ in the proof.
• Right below that, in Exercise 13.2, they give some hints as for what you should be looking at if you'd like to derive the modified proof for the case where $\gamma < 1$.

Answer 3

It's a subtle issue.

If you look at the A3C algorithm in the original paper (p.4 and appendix S3 for pseudo-code), their actor-critic algorithm (same algorithm both episodic and continuing problems) is off by a factor of gamma relative to the actor-critic pseudo-code for episodic problems in the Sutton and Barto book (p.332 of January 2019 edition of http://incompleteideas.net/book/the-book.html). The Sutton and Barto book has the extra "first" gamma as labeled in your picture. So, either the book or the A3C paper is wrong? Not really.

The key is on p. 199 of the Sutton and Barto book:

If there is discounting (gamma < 1) it should be treated as a form of termination, which can be done simply by including a factor of in the second term of (9.2).

The subtle issue is that there are two interpretations to the discounting factor gamma:

1. A multiplicative factor that puts less weight on distant future rewards.
2. A probability, 1 - gamma, that a simulated trajectory spuriously terminates, at any time step. This interpretation only makes sense for episodic cases, and not continuing cases.

Literal implementations:

1. Just multiply the future rewards and related quantities (V or Q) in the future by gamma.
2. Simulate some trajectories and randomly terminate (1 - gamma) of them at each time step. Terminated trajectories give no immediate or future rewards.

The two interpretations of gamma are valid. But choosing one or the other means you are tackling a different problem. The math is slightly different and you end up with an extra gamma multiplying $G \nabla\ln\pi(a|s)$ with the second interpretation.

For example, if you are at step t=2 and gamma = 0.9, the algorithm for the second interpretation is that the policy gradient is $\gamma^2 G \nabla\ln\pi(a|s)$ or $0.81 G \nabla\ln\pi(a|s)$. This term has 19% less gradient power than the t=0 term for the simple reason that 19% of simulated trajectories have died off by t=2.

With the first interpretation of gamma, there is no such 19% decay. The policy gradient is just $G \nabla\ln\pi(a|s)$ at t=2. But gamma is still present within $G$ to discount the future rewards.

You can choose whichever interpretation of gamma, but you have to be mindful of the consequences to the algorithm. I personally prefer to stick with interpretation 1 just because it's simpler. So I use the algorithm in the A3C paper, not the Sutton and Barto book.

Your question was about the REINFORCE algorithm, but I have been discussing actor-critic. You have the exact same issue related to the two gamma interpretations and the extra gamma in REINFORCE.

Answer 4

I would like to follow up on @toto2's answer about the first interpretation of gamma. (I'm a new user and can't post a comment.)

Does it make sense to include $\gamma$ in the return and the state and action value functions without considering it as part of the MDP? (interpretation 2).

If one derives the policy gradient with respect to the discounted return as the objective, then the discounted state distribution arises (the one corresponding to interpretation 2), not the original one. Proof here.

This seems to mean that you can't have interpretation 1 without interpretation 2.

I would be happy to discuss this further.