# $\gamma^t$ in REINFORCE update (Sutton-Barto RL book Exercise 13.2)

I've struggled with solving exercise 13.2 from Reinforcement Learning: An Introduction Second Edition :

Generalize the box on page 199, the policy gradient theorem (13.5), the proof of the policy gradient theorem (page 325), and the steps leading to the REINFORCE update equation (13.8), so that (13.8) ends up with a factor of $$\gamma^t$$ and thus aligns with the general algorithm given in the pseudocode.

Below is my attempt. Please let me know if this is correct or where I've made a mistake (exercise 13.2 was was not in the authors' official solutions when I checked).

Generalize box on 199

As explained in the box on 199, include a factor of $$\gamma$$ in the second term of (9.2):

$$\eta_\gamma(s) = h(s) + \gamma \sum_{\overline{s}} \eta(\overline{s}) \sum_a \pi(a|\overline{s}) p(s|\overline{s},a)$$

$$\mu_\gamma(s) = \frac{\eta_\gamma(s)}{\sum_{s^\prime} \eta(s^\prime)}$$

I initially thought the definition of $$\mu_\gamma(s)$$ was

$$\mu_\gamma(s) = \frac{\eta_\gamma(s)}{\sum_{s^\prime} \eta_\gamma(s^\prime)}$$

but I could not see how to finish the exercise with this definition. Given that we are assuming a single starting state $$s_0$$, we can also write $$\eta_\gamma(s)$$ as:

$$\eta_\gamma(s) = \sum_{k=0}^\infty \gamma^k Pr(s_0 \rightarrow s, k, \pi)$$

Generalize Proof of the Policy Gradient Theorem (episodic case)

I followed the steps in the proof on page 325 and added discounting.

\begin{aligned} \nabla v_\pi(s) &= \nabla \bigg[\sum_a \pi(a|s) q_\pi(s,a)\bigg] \text{,} \quad \text{for all} \; s \in \mathcal{S} \\ &= \sum_a \bigg[\nabla \pi(a|s) q_\pi(s,a) + \pi(a|s) \nabla q_\pi(s,a)\bigg] \\ &= \sum_a \bigg[\nabla \pi(a|s) q_\pi(s,a) + \pi(a|s) \nabla \sum_{s^\prime,r} p(s^\prime,r|s,a) (r + \gamma v_\pi(s^\prime))\bigg] \\ &= \sum_a \bigg[\nabla \pi(a|s) q_\pi(s,a) + \gamma \pi(a|s) \sum_{s^\prime} p(s^\prime|s,a) \nabla v_\pi(s^\prime)\bigg] \\ &= \sum_a \bigg[\nabla \pi(a|s) q_\pi(s,a) + \gamma \pi(a|s) \sum_{s^\prime} p(s^\prime|s,a) \sum_{a^\prime} \big[\nabla \pi(a^\prime|s^\prime) q_\pi(s^\prime,a^\prime) + \gamma \pi(a^\prime|s^\prime) \sum_{s^{\prime\prime}} p(s^{\prime\prime}|s^\prime,a^\prime) \nabla v_\pi(s^{\prime\prime})\big]\bigg] \\ &= \sum_{x \in \mathcal{S}} \sum_{k=0}^\infty \gamma^k Pr(s \rightarrow x, k, \pi) \sum_a \nabla \pi(a|x) q_\pi(x,a) \end{aligned}

\begin{aligned} \nabla J(\theta) &= \nabla v_\pi(s_0) \\ &= \sum_s \bigg(\sum_{k=0}^\infty \gamma^k Pr(s_0 \rightarrow s, k, \pi)\bigg) \sum_a \nabla \pi(a|s) q_\pi(s,a) \\ &= \sum_s \eta_\gamma(s) \sum_a \nabla \pi(a|s) q_\pi(s,a) \\ &= \sum_{s^\prime} \eta(s^\prime) \sum_s \frac{\eta_\gamma(s)}{\sum_{s^\prime} \eta(s^\prime)} \sum_a \nabla \pi(a|s) q_\pi(s,a) \\ &= \sum_{s^\prime} \eta_\gamma(s^\prime) \sum_s \mu_\gamma(s) \sum_a \nabla \pi(a|s) q_\pi(s,a) \\ &\propto \sum_s \mu_\gamma(s) \sum_a \nabla \pi(a|s) q_\pi(s,a) \end{aligned}

Steps leading to the REINFORCE update equation (13.8)

\begin{aligned} \nabla J(\boldsymbol{\theta}) &\propto \sum_s \mu_\gamma(s) \sum_a q_\pi(s,a,\boldsymbol{\theta}) \nabla \pi(a|s) \\ &= \mathbb{E}_\pi\bigg[\gamma^t \sum_a \pi(a|S_t,\boldsymbol{\theta}) q_\pi(S_t,a) \frac{\nabla \pi(a|S_t,\boldsymbol{\theta})}{\pi(a|S_t,\boldsymbol{\theta})}\bigg] \\ &= \mathbb{E}_\pi\bigg[\gamma^t q_\pi(S_t,A_t) \frac{\nabla \pi(A_t|S_t,\boldsymbol{\theta})}{\pi(A_t|S_t,\boldsymbol{\theta})}\bigg] \\ &= \mathbb{E}_\pi\bigg[\gamma^t G_t \frac{\nabla \pi(A_t|S_t,\boldsymbol{\theta})}{\pi(A_t|S_t,\boldsymbol{\theta})}\bigg] \end{aligned}

Discounted REINFORCE update:

\begin{aligned} \boldsymbol{\theta}_{t+1} &\overset{.}{=} \boldsymbol{\theta}_t + \alpha \gamma^t G_t \frac{\nabla \pi(A_t|S_t,\boldsymbol{\theta})}{\pi(A_t|S_t,\boldsymbol{\theta})} \\ &= \boldsymbol{\theta}_t + \alpha \gamma^t G_t \nabla \ln\pi(A_t|S_t,\boldsymbol{\theta}) \end{aligned}

I dont understand why the $$\gamma^t$$ appears when you write the gradient with an expectation. Could you elaborate ? thank you

I agree with you with all the things up to that point

EDIT : to try to answer my own question, I would say that it is important to clarify what the expectation is based on :

\begin{align} \sum\limits_s \mu_\pi(s) \sum\limits_a q_\pi(s,a) \nabla_\theta \pi(a|s) &= \mathbb{E}_{s \sim \mu_\pi} \big[ \sum\limits_a q_\pi(s,a) \nabla_\theta \log \pi(a|s)\big]\\ &= \mathbb{E_\pi} \big[\gamma^t \sum\limits_a q_\pi(S_t,a) \nabla_\theta \log \pi(a|S_t) \big] \end{align}

in the first, we use the on-policy undiscounted state distribution, which is not exactly the same as the discounted state distribution, as my understanding of it. See : https://proceedings.mlr.press/v202/che23a/che23a.pdf

• With $\mathbb{E}_\pi$ I meant the on-policy undiscounted expectation. Since $\mu_\gamma$ is the discounted distribution, I believe we are left with a factor of $\gamma^t$ when rewriting as $\mathbb{E}_\pi$. However, this part is what I was (and still is) the most unsure about.
– cfml
Commented Sep 11, 2023 at 19:05
• So yes I agree with what you've done, but like you I'm not 100% sure. As pointed out in the paper linked and in towardsdatascience.com/…, I think it's something a lot of people overlook Commented Sep 12, 2023 at 20:27

We just need to exchange the order of summation and then sample episodes in both space and time to perform gradient descent. My response is a bit late, but I hope it can still be of help to you.