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

Question

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} $$

Answer 1

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

Answer 2

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.

Answer 3

Went back to this question a year after, and after carefully reading your derivation, I don't understand why you can't define :

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

Here is the start of your derivation :

\begin{align} \nabla v_\pi(s_0) &= \sum_s \eta_\gamma(s) \sum_a \nabla \pi(a|s) q_\pi(s,a) \\ &= \sum_{s'} \eta(s') \sum_s \frac{\eta_\gamma(s)}{\sum_{s'}\eta(s')} \sum_a \nabla \pi(a|s) q_\pi(s,a) \\ &= \sum_{s'} \eta_\gamma(s') \sum_s \mu_\gamma(s) \sum_a \nabla \pi(a|s) q_\pi(s,a) \end{align}

going from line 1 to line 2 is multiplying by $\frac{\sum_{s'} \eta(s')}{\sum_{s'} \eta(s')}$

going from line 2 to line 3 is using your definition of $\mu_\gamma(s)$ but I don't see why you also changed the $\eta(s')$ into $\eta_\gamma(s')$ ?

If you use the $\mu_{\gamma}(s) = \frac{\eta_\gamma(s)}{\sum_{s'} \eta_\gamma(s')}$ definition in the first place, you just straight away multiply by $\frac{\sum_{s'} \eta_\gamma(s')}{\sum_{s'} \eta_\gamma(s')}$ and I don't see any problem to finish the proof.