Answers.Body: <p>I dont understand why the <span class="math-container">$\gamma^t$</span> appears when you write the gradient with an expectation. Could you elaborate ? thank you</p>
  <p>I agree with you with all the things up to that point</p>
  <p>EDIT : to try to answer my own question, I would say that it is important to clarify what the expectation is based on :</p>
  <p><span class="math-container">\begin{align}
  \sum\limits_s \mu_\pi(s) \sum\limits_a q_\pi(s,a) \nabla_\theta \pi(a|s) &amp;= \mathbb{E}_{s \sim \mu_\pi} \big[ \sum\limits_a q_\pi(s,a) \nabla_\theta \log \pi(a|s)\big]\\
  &amp;= \mathbb{E_\pi} \big[\gamma^t \sum\limits_a q_\pi(S_t,a) \nabla_\theta \log \pi(a|S_t) \big]
  \end{align}</span></p>
  <p>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 : <a href="https://proceedings.mlr.press/v202/che23a/che23a.pdf" rel="nofollow noreferrer">https://proceedings.mlr.press/v202/che23a/che23a.pdf</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-11T19:05:14.040Z
Answers.Text: 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.
Answers.UserDisplayName: cfml
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-12T20:27:23.357Z
Answers.Text: 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 https://towardsdatascience.com/why-there-is-a-problem-with-the-policy-gradient-theorem-in-deep-reinforcement-learning-958d845218f1, I think it's something a lot of people overlook
Answers.UserDisplayName: Procuste
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-09T15:38:38.810Z
Answers.LastActivityDate: 2023-09-09T19:41:27.013Z
Answers.LastEditDate: 2023-09-09T19:41:27.013Z
Answers.UserDisplayName: Procuste
Answers.Body: <p>Went back to this question a year after, and after carefully reading your derivation, I don't understand why you can't define :</p>
  <p><span class="math-container">$$\mu_{\gamma}(s) = \frac{\eta_\gamma(s)}{\sum_{s'} \eta_\gamma(s')}$$</span></p>
  <p>Here is the start of your derivation :</p>
  <p><span class="math-container">\begin{align}
  \nabla v_\pi(s_0) &amp;= \sum_s \eta_\gamma(s) \sum_a \nabla \pi(a|s) q_\pi(s,a) \\
  &amp;= \sum_{s'} \eta(s') \sum_s \frac{\eta_\gamma(s)}{\sum_{s'}\eta(s')} \sum_a \nabla \pi(a|s) q_\pi(s,a) \\
  &amp;= \sum_{s'} \eta_\gamma(s') \sum_s \mu_\gamma(s) \sum_a \nabla \pi(a|s) q_\pi(s,a)
  \end{align}</span></p>
  <p>going from line 1 to line 2 is multiplying by <span class="math-container">$\frac{\sum_{s'} \eta(s')}{\sum_{s'} \eta(s')}$</span></p>
  <p>going from line 2 to line 3 is using your definition of <span class="math-container">$\mu_\gamma(s)$</span> but I don't see why you also changed the <span class="math-container">$\eta(s')$</span> into <span class="math-container">$\eta_\gamma(s')$</span> ?</p>
  <p>If you use the <span class="math-container">$\mu_{\gamma}(s) = \frac{\eta_\gamma(s)}{\sum_{s'} \eta_\gamma(s')}$</span> definition in the first place, you just straight away multiply by <span class="math-container">$\frac{\sum_{s'} \eta_\gamma(s')}{\sum_{s'} \eta_\gamma(s')}$</span> and I don't see any problem to finish the proof.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-28T08:26:38.477Z
Answers.LastActivityDate: 2024-09-28T08:26:38.477Z
Answers.UserDisplayName: Procuste
Answers.Body: <p>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.</p>
  <p><a href="https://i.sstatic.net/trDzBCpy.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/trDzBCpy.png" alt="enter image description here" /></a></p>
  <p><a href="https://i.sstatic.net/YjSseVBx.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/YjSseVBx.png" alt="enter image description here" /></a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-28T17:18:15.867Z
Answers.LastActivityDate: 2024-04-29T11:03:34.917Z
Answers.LastEditDate: 2024-04-29T11:03:34.917Z
Answers.UserDisplayName: Jax
Body: <p>I've struggled with solving exercise 13.2 from <a href="http://incompleteideas.net/book/the-book-2nd.html" rel="nofollow noreferrer">Reinforcement Learning: An Introduction Second Edition</a> :</p>
  <blockquote>
  <p>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 <span class="math-container">$\gamma^t$</span> and thus aligns with the general algorithm given
  in the pseudocode.</p>
  </blockquote>
  <p>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).</p>
  <p><strong>Generalize box on 199</strong></p>
  <p>As explained in the box on 199, include a factor of <span class="math-container">$\gamma$</span>  in the second term of (9.2):</p>
  <p><span class="math-container">$$
  \eta_\gamma(s) = h(s) + \gamma \sum_{\overline{s}} \eta(\overline{s}) \sum_a \pi(a|\overline{s}) p(s|\overline{s},a)
  $$</span></p>
  <p><span class="math-container">$$
  \mu_\gamma(s) = \frac{\eta_\gamma(s)}{\sum_{s^\prime} \eta(s^\prime)}
  $$</span></p>
  <p>I initially thought the definition of <span class="math-container">$\mu_\gamma(s)$</span> was</p>
  <p><span class="math-container">$$
  \mu_\gamma(s) = \frac{\eta_\gamma(s)}{\sum_{s^\prime} \eta_\gamma(s^\prime)}
  $$</span></p>
  <p>but I could not see how to finish the exercise with this definition. Given that we are assuming a single starting state <span class="math-container">$s_0$</span>, we can also write <span class="math-container">$\eta_\gamma(s)$</span> as:</p>
  <p><span class="math-container">$$
  \eta_\gamma(s) = \sum_{k=0}^\infty \gamma^k Pr(s_0 \rightarrow s, k, \pi)
  $$</span></p>
  <p><strong>Generalize Proof of the Policy Gradient Theorem (episodic case)</strong></p>
  <p>I followed the steps in the proof on page 325 and added discounting.</p>
  <p><span class="math-container">$$
  \begin{aligned}
  \nabla v_\pi(s) &amp;= \nabla \bigg[\sum_a \pi(a|s) q_\pi(s,a)\bigg] \text{,} \quad \text{for all} \; s \in \mathcal{S} \\
  &amp;= \sum_a \bigg[\nabla \pi(a|s) q_\pi(s,a) + \pi(a|s) \nabla q_\pi(s,a)\bigg] \\
  &amp;= \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] \\
  &amp;= \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] \\
  &amp;= \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] \\
  &amp;= \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}
  $$</span></p>
  <p><span class="math-container">$$
  \begin{aligned}
  \nabla J(\theta) &amp;= \nabla v_\pi(s_0) \\
  &amp;= \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) \\
  &amp;= \sum_s \eta_\gamma(s) \sum_a \nabla \pi(a|s) q_\pi(s,a) \\
  &amp;= \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) \\
  &amp;= \sum_{s^\prime} \eta_\gamma(s^\prime) \sum_s \mu_\gamma(s) \sum_a \nabla \pi(a|s) q_\pi(s,a) \\
  &amp;\propto \sum_s \mu_\gamma(s) \sum_a \nabla \pi(a|s) q_\pi(s,a)
  \end{aligned}
  $$</span></p>
  <p><strong>Steps leading to the REINFORCE update equation (13.8)</strong></p>
  <p><span class="math-container">$$
  \begin{aligned}
  \nabla J(\boldsymbol{\theta}) &amp;\propto \sum_s \mu_\gamma(s) \sum_a q_\pi(s,a,\boldsymbol{\theta}) \nabla \pi(a|s) \\
  &amp;= \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] \\
  &amp;= \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] \\
  &amp;= \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}
  $$</span></p>
  <p>Discounted REINFORCE update:</p>
  <p><span class="math-container">$$
  \begin{aligned}
  \boldsymbol{\theta}_{t+1} &amp;\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})} \\
  &amp;= \boldsymbol{\theta}_t + \alpha \gamma^t G_t \nabla \ln\pi(A_t|S_t,\boldsymbol{\theta})
  \end{aligned}
  $$</span></p>
  
Tags: <reinforcement-learning><policy-gradients><proofs><sutton-barto><reinforce>
Title: $\gamma^t$ in REINFORCE update (Sutton-Barto RL book Exercise 13.2)
UserDisplayName: cfml
ThreadText: # $\gamma^t$ in REINFORCE update (Sutton-Barto RL book Exercise 13.2)
  
  (Asked by: username_0 on 2023-06-18)
  
  I've struggled with solving exercise 13.2 from [Reinforcement Learning: An Introduction Second Edition](http://incompleteideas.net/book/the-book-2nd.html) :
  
  > 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}
  $$
  
  **Tags:** reinforcement-learning, policy-gradients, proofs, sutton-barto, reinforce
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2023-09-09. Score: 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>
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_1**: 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 https://towardsdatascience.com/why-there-is-a-problem-with-the-policy-gradient-theorem-in-deep-reinforcement-learning-958d845218f1, I think it's something a lot of people overlook  
  
  ---
  
  ### Answer by username_1 on 2024-09-28. Score: 0
  
  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.
  
  
  ---
  
  ### Answer by username_2 on 2024-04-28. Score: 0
  
  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.
  
  [![enter image description here](https://i.sstatic.net/trDzBCpy.png)](https://i.sstatic.net/trDzBCpy.png)
  
  [![enter image description here](https://i.sstatic.net/YjSseVBx.png)](https://i.sstatic.net/YjSseVBx.png)
  
  
  ---
  
  