Answers.Body: <p>A correct proof is given at <a href="https://spinningup.openai.com/en/latest/spinningup/extra_pg_proof1.html" rel="nofollow noreferrer">https://spinningup.openai.com/en/latest/spinningup/extra_pg_proof1.html</a>.
  It uses, among other techniques, the probability chain rule.</p>
  <p>On the contrary, an attempt to prove &quot;reward to go&quot; by applying
  <span class="math-container">$ X, Y \: independent \implies E[XY] = E[X]E[Y]$</span> does not work.</p>
  <p>The random variables
  <span class="math-container">$ \sum_{t'=1}^{t-1} r(s_{t'}, a_{t'}) $</span>
  and
  <span class="math-container">$ \nabla_{\theta} \log \pi_{\theta} (a_t \mid s_t) $</span>
  are generally not independent.
  They would be independent, if
  <span class="math-container">$ P[ \nabla_{\theta} \log \pi_{\theta} (a_t \mid s_t) \mid \sum_{t'=1}^{t-1} r(s_{t'}, a_{t'}) ] = P[ \nabla_{\theta} \log \pi_{\theta} (a_t \mid s_t) ] $</span> but this does not follow from
  <span class="math-container">$ \pi_{\theta}(a_t \mid s_t) = \pi_{\theta}(a_t \mid s_t, s_{t-1},...,s_1,a_{t-1}, ..., a_1) $</span></p>
  <p>Consider the following setup as an example for the dependency between the two random variables in question.</p>
  <p>times = {1, 2, 3, ..., T}</p>
  <p>states = {1, 2, 3, ..., T}</p>
  <p>actions = {0, 1}</p>
  <p><span class="math-container">$ \pi(a_t = 0 \mid s_t) = \frac{1}{s_t} $</span></p>
  <p><span class="math-container">$ r(s_t, a_t) = 1 $</span>
  i.e. the event reward at time t equals 1
  and the total reward from time 1 to time t-1 equals t-1</p>
  <p><span class="math-container">$ P(s_1 = 1) = 1 $</span>
  i.e. all trajectories start in state 1</p>
  <p><span class="math-container">$ P(s_{t+1} = s_t + 1 \mid s_t, a_t) = 1 $</span>
  i.e. the next state, given the current state and the current action, is always the current state + 1</p>
  <p>As a result,
  the higher time <span class="math-container">$ t $</span>,
  the higher the state <span class="math-container">$ s_t $</span>,
  the higher the probability for action <span class="math-container">$ a_t = 1 $</span> and the higher the total reward from time <span class="math-container">$ 0 $</span> to time <span class="math-container">$ t-1 $</span>,
  i.e. the values of <span class="math-container">$ \pi(a_t \mid s_t) $</span> and thus the values of <span class="math-container">$ \nabla_{\theta} \log \pi (a_t \mid s_t) $</span>
  are highly correlated with the total rewards from time <span class="math-container">$ 0 $</span> to time <span class="math-container">$ t-1 $</span>,
  hence respective random variables are not independent of each other.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-27T14:36:09.573Z
Answers.LastActivityDate: 2022-09-27T14:36:09.573Z
Answers.UserDisplayName: blubb3456
Answers.Body: <p>By linearity of expection and using the distributive property:</p>
  <p><span class="math-container">$$\begin{align} \nabla_{\boldsymbol{\theta}} J(\boldsymbol{\theta}) &amp;= \mathbb{E}_{\tau \sim p_{\boldsymbol{\theta}}(\tau)} \left[ \left( \sum_{t=1}^T \nabla_{\theta} \log \pi_{\theta} (\mathbf{a}_t \mid \mathbf{s}_t) \right) \left( \sum_{t=1}^T r(\mathbf{s}_{t}, \mathbf{a}_{t}) \right) \right] \\ &amp;= \sum_{t=1}^T \mathbb{E}_{\tau \sim p_{\boldsymbol{\theta}}(\tau)} \left[    \nabla_{\theta} \log \pi_{\boldsymbol{\theta}} (\mathbf{a}_t \mid \mathbf{s}_t)    \sum_{t'=1}^T r(\mathbf{s}_{t'}, \mathbf{a}_{t'})  \right] \\  &amp;= \sum_{t=1}^T \mathbb{E}_{\tau \sim p_{\boldsymbol{\theta}}(\tau)} \left[    \nabla_{\theta} \log \pi_{\boldsymbol{\theta}} (\mathbf{a}_t \mid \mathbf{s}_t)    \sum_{t'=1}^{t-1} r(\mathbf{s}_{t'}, \mathbf{a}_{t'}) +\nabla_{\theta} \log \pi_{\boldsymbol{\theta}} (\mathbf{a}_t \mid \mathbf{s}_t)    \sum_{t'=t}^T r(\mathbf{s}_{t'}, \mathbf{a}_{t'})  \right] \\ &amp; = \sum_{t=1}^T \sum_{t'=1}^{t-1}\mathbb{E}_{\tau \sim p_{\boldsymbol{\theta}}(\tau)} \left[ \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}} (\mathbf{a}_t \mid \mathbf{s}_t) \, r(\mathbf{s}_{t'}, \mathbf{a}_{t'}) \right] +\sum_{t=1}^T \mathbb{E}_{\tau \sim p_{\boldsymbol{\theta}}(\tau)} \left[ \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}} (\mathbf{a}_t \mid \mathbf{s}_t) \,\sum_{t'=t}^T  r(\mathbf{s}_{t'}, \mathbf{a}_{t'}) \right]\\ \end{align}$$</span></p>
  <p>and the first term can be further expanded as follows:</p>
  <p><span class="math-container">$$\begin{align} &amp;\sum_{t=1}^T \sum_{t'=1}^{t-1}\mathbb{E}_{\tau \sim p_{\boldsymbol{\theta}}(\tau)} \left[ \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}} (\mathbf{a}_t \mid \mathbf{s}_t) \, r(\mathbf{s}_{t'}, \mathbf{a}_{t'}) \right] \\ = &amp;\sum_{t=1}^T \sum_{t'=1}^{t-1} \mathbb{E}_{(\mathbf{s}_{t}, \mathbf{a}_{t}, \mathbf{s}_{t'}, \mathbf{a}_{t'}) \sim p_{\boldsymbol{\theta}}(\mathbf{s}_{t}, \mathbf{a}_{t}, \mathbf{s}_{t'}, \mathbf{a}_{t'})} \left[ \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}} (\mathbf{a}_t \mid \mathbf{s}_t) \, r(\mathbf{s}_{t'}, \mathbf{a}_{t'}) \right]  \\ = &amp;\sum_{t=1}^T \sum_{t'=1}^{t-1}  \mathbb{E}_{(\mathbf{s}_{t'}, \mathbf{a}_{t'}) \sim p_{\boldsymbol{\theta}}(\mathbf{s}_{t'}, \mathbf{a}_{t'})}  \left[\mathbb{E}_{(\mathbf{s}_{t}, \mathbf{a}_{t}) \sim p_{\boldsymbol{\theta}}(\mathbf{s}_{t}, \mathbf{a}_{t} \mid \mathbf{s}_{t'}, \mathbf{a}_{t'})} \left[ \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}} (\mathbf{a}_t \mid \mathbf{s}_t) \, r(\mathbf{s}_{t'}, \mathbf{a}_{t'}) \right] \right] \\ = &amp;\sum_{t=1}^T \sum_{t'=1}^{t-1}  \mathbb{E}_{(\mathbf{s}_{t'}, \mathbf{a}_{t'}) \sim p_{\boldsymbol{\theta}}(\mathbf{s}_{t'}, \mathbf{a}_{t'})}  \left[  r(\mathbf{s}_{t'}, \mathbf{a}_{t'}) \; \mathbb{E}_{(\mathbf{s}_{t}, \mathbf{a}_{t}) \sim p_{\boldsymbol{\theta}}(\mathbf{s}_{t}, \mathbf{a}_{t} \mid \mathbf{s}_{t'}, \mathbf{a}_{t'})} \left[ \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}} (\mathbf{a}_t \mid \mathbf{s}_t) \,\right] \right] \\ \end{align}
  $$</span></p>
  <p>The innermost expectation can be broken down further into
  <span class="math-container">$$\mathbb{E}_{(\mathbf{s}_{t}, \mathbf{a}_{t}) \sim p_{\boldsymbol{\theta}}(\mathbf{s}_{t}, \mathbf{a}_{t} \mid \mathbf{s}_{t'}, \mathbf{a}_{t'})} \left[ \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}} (\mathbf{a}_t \mid \mathbf{s}_t)  \right]\\ = \int  \int  \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}} (\mathbf{a}_t \mid \mathbf{s}_t) \,\pi_{\boldsymbol{\theta}}(\mathbf{a}_t \mid \mathbf{s}_t) \, \, p(\mathbf{s}_{t} \mid \mathbf{s}_{t'}, \mathbf{a}_{t'})\, d\mathbf{a}_t \; d \mathbf{s}_t \\
  = \int  p(\mathbf{s}_{t} \mid \mathbf{s}_{t'}, \mathbf{a}_{t'}) \int  \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}} (\mathbf{a}_t \mid \mathbf{s}_t) \,\pi_{\boldsymbol{\theta}}(\mathbf{a}_t \mid \mathbf{s}_t) \,   d\mathbf{a}_t \; d \mathbf{s}_t$$</span></p>
  <p>where <span class="math-container">$ \int  \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}} (\mathbf{a}_t \mid \mathbf{s}_t) \,\pi_{\boldsymbol{\theta}}(\mathbf{a}_t \mid \mathbf{s}_t) \,   d\mathbf{a}_t = \mathbb{E}_{ \mathbf{a}_{t} \sim \pi_{\boldsymbol{\theta}}( \mathbf{a}_{t} \mid \mathbf{s}_{t})} \left[ \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}} (\mathbf{a}_t \mid \mathbf{s}_t)  \right]  =0$</span> due to the <a href="https://spinningup.openai.com/en/latest/spinningup/rl_intro3.html#expected-grad-log-prob-lemma" rel="nofollow noreferrer">EGLP lemma</a></p>
  <p>As a result,  we have
  <span class="math-container">$$\nabla_{\boldsymbol{\theta}} J(\boldsymbol{\theta}) = \sum_{t=1}^T \mathbb{E}_{\tau \sim p_{\boldsymbol{\theta}}(\tau)} \left[ \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}} (\mathbf{a}_t \mid \mathbf{s}_t) \,\sum_{t'=t}^T  r(\mathbf{s}_{t'}, \mathbf{a}_{t'}) \right]
  $$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-05T15:45:19.113Z
Answers.LastActivityDate: 2024-01-05T15:52:01.987Z
Answers.LastEditDate: 2024-01-05T15:52:01.987Z
Answers.UserDisplayName: Jus Forever
Answers.Body: <p>An important thing we're going to need is what is called the <a href="https://spinningup.openai.com/en/latest/spinningup/rl_intro3.html#expected-grad-log-prob-lemma" rel="noreferrer">&quot;Expected Grad-Log-Prob Lemma here&quot;</a> (proof included on that page), which says that (for any <span class="math-container">$t$</span>):</p>
  <p><span class="math-container">$$\mathbb{E}_{\tau \sim \pi_{\theta}(\tau)} \left[ \nabla_{\theta} \log \pi_{\theta}(a_t \mid s_t) \right] = 0.$$</span></p>
  <p>Taking the analytical expression of the gradient (from, for example, slide 9) as a starting point:</p>
  <p><span class="math-container">$$\begin{aligned}
  \nabla_{\theta} J(\theta) &amp;= \mathbb{E}_{\tau \sim \pi_{\theta}(\tau)} \left[ \left( \sum_{t=1}^T \nabla_{\theta} \log \pi_{\theta} (a_t \mid s_t) \right) \left( \sum_{t=1}^T r(s_t, a_t) \right) \right] \\
  %
  &amp;= \sum_{t=1}^T \mathbb{E}_{\tau \sim \pi_{\theta}(\tau)} \left[ \nabla_{\theta} \log \pi_{\theta} (a_t \mid s_t) \sum_{t'=1}^T r(s_{t'}, a_{t'}) \right] \\
  %
  &amp;= \sum_{t=1}^T \mathbb{E}_{\tau \sim \pi_{\theta}(\tau)} \left[ \nabla_{\theta} \log \pi_{\theta} (a_t \mid s_t) \sum_{t'=1}^{t-1} r(s_{t'}, a_{t'}) + \nabla_{\theta} \log \pi_{\theta} (a_t \mid s_t) \sum_{t'=t}^T r(s_{t'}, a_{t'}) \right] \\
  %
  &amp;= \sum_{t=1}^T \left( \mathbb{E}_{\tau \sim \pi_{\theta}(\tau)} \left[ \nabla_{\theta} \log \pi_{\theta} (a_t \mid s_t) \sum_{t'=1}^{t-1} r(s_{t'}, a_{t'}) \right] \\
  + \mathbb{E}_{\tau \sim \pi_{\theta}(\tau)} \left[ \nabla_{\theta} \log \pi_{\theta} (a_t \mid s_t) \sum_{t'=t}^T r(s_{t'}, a_{t'}) \right] \right) \\
  \end{aligned}$$</span></p>
  <p>At the <span class="math-container">$t^{th}$</span> &quot;iteration&quot; of the outer sum, the random variables
  <span class="math-container">$ \sum_{t'=1}^{t-1} r(s_{t'}, a_{t'}) $</span>
  and
  <span class="math-container">$ \nabla_{\theta} \log \pi_{\theta} (a_t \mid s_t) $</span>
  are independent (we assume, by definition, the action only depends on the most recent state), which means we are allowed to split the expectation:</p>
  <p><span class="math-container">$$\nabla_{\theta} J(\theta) = \sum_{t=1}^T \left( \mathbb{E}_{\tau \sim \pi_{\theta}(\tau)} \left[ \sum_{t'=1}^{t-1} r(s_{t'}, a_{t'}) \right] \mathbb{E}_{\tau \sim \pi_{\theta}(\tau)} \left[ \nabla_{\theta} \log \pi_{\theta} (a_t \mid s_t) \right] \\
  + \mathbb{E}_{\tau \sim \pi_{\theta}(\tau)} \left[ \nabla_{\theta} \log \pi_{\theta} (a_t \mid s_t) \sum_{t'=t}^T r(s_{t'}, a_{t'}) \right] \right)$$</span></p>
  <p>The first expectation can now be replaced by <span class="math-container">$0$</span> due to the lemma mentioned at the top of the post:</p>
  <p><span class="math-container">$$
  \begin{aligned}
  \nabla_{\theta} J(\theta)
  %
  &amp;= \sum_{t=1}^T \mathbb{E}_{\tau \sim \pi_{\theta}(\tau)} \left[ \nabla_{\theta} \log \pi_{\theta} (a_t \mid s_t) \sum_{t'=t}^T r(s_{t'}, a_{t'}) \right]  \\
  %
  &amp;= \mathbb{E}_{\tau \sim \pi_{\theta}(\tau)} \sum_{t=1}^T \nabla_{\theta} \log \pi_{\theta} (a_t \mid s_t) \left( \sum_{t'=t}^T r(s_{t'}, a_{t'}) \right). \\
  \end{aligned}
  $$</span></p>
  <p>The expression on slide 18 of the linked slides is an unbiased, sample-based estimator of this gradient:</p>
  <p><span class="math-container">$$\nabla_{\theta} J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_{\theta} \log \pi_{\theta} (a_{i, t} \mid s_{i, t}) \left( \sum_{t'=t}^T r(s_{i, t'}, a_{i, t'}) \right)$$</span></p>
  <hr />
  <p>For a more formal treatment of the claim that we can pull <span class="math-container">$\sum_{t'=1}^{t-1} r(s_{t'}, a_{t'})$</span> out of an expectation due to the Markov property, see this page: <a href="https://spinningup.openai.com/en/latest/spinningup/extra_pg_proof1.html" rel="noreferrer">https://spinningup.openai.com/en/latest/spinningup/extra_pg_proof1.html</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-04T03:09:21.763Z
Answers.Text: Why is the form of "Expected Grad-Log-Prob Lemma" mentioned at the top of the post legit? It is different than the form of the proof shown in the link (the proof in the link has no problem). Your lemma is an expectation over **trajectories**.
Answers.UserDisplayName: starriet 차주녕
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-04T09:43:56.817Z
Answers.Text: @starriet For the individual choice of a single action at one point in time within a trajectory, the trajectory as a whole has no influence (our policy does not look at the history or the future, just at the current state), so $\mathbb{E}_{\tau \sim \pi_{\theta}(\tau)} \left[ \nabla_{\theta} \log \pi_{\theta} (a_t \mid s_t) \right] = \mathbb{E}_{a_t \sim \pi_{\theta}} \left[ \nabla_{\theta} \log \pi_{\theta} (a_t \mid s_t) \right]$, where the right-hand side more closely matches that notation from the link.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-04T09:45:09.773Z
Answers.Text: @starriet However, we use the trajectory-based notation because in the larger equation, we have these sums over all time steps, and that's the part where the full trajectory actually becomes relevant.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-04T12:41:28.200Z
Answers.Text: Thanks, I think I got your point. If I understood correctly, the right-hand side is at a *specific state*, and the left-hand side is at the various states and actions of *all possible trajectories*, right? Since the RHS is 0 and it's about one state, LHS is also 0 because LHS is an expectation over all states (this is how I understood. please let me know if I'm wrong).
Answers.UserDisplayName: starriet 차주녕
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-04T12:51:46.637Z
Answers.Text: But still, It's difficult to understand why the form of the LHS is legit. It's an expectation over trajectories, but the term inside of the square bracket is a function of action and state. Given that a trajectory is composed of many states and actions, how the expectation over trajectories is possible if the term inside of the brackets is smaller than a trajectory?
Answers.UserDisplayName: starriet 차주녕
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-04T12:59:14.390Z
Answers.Text: @starriet Suppose that we have a "trajectory" $\tau$ where we roll 100 dice in a row. Forget about RL and actions and policies for a moment, just rolling 100 dice in a row. These dice rolls are independent of each other, so the expected value of any individual roll $x_t$ is $\mathbb{E}_{x_{t} \sim \text{dice-roll}} [ x_t ] = 3.5$. Here we take the expectation over just that single dice-roll event. We can also take it over the entire trajectory of all rolls though, but it won't change anything since they're independent: $\mathbb{E}_{\tau \sim \text{100 dice-rolls}} [ x_t ] = 3.5$.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-04T13:00:14.477Z
Answers.Text: @starriet So here in RL with the actions it's kind of a similar idea. The expectation taken over the entire trajectory takes lots of extra irrelevant information into account which doesn't change anything due to independence (but it's convenient because we do need that "bigger" expectation elsewhere in the equation)
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-26T01:37:14.787Z
Answers.Text: This answer brought me closer to Enlightenment. Thanks Dennis.
Answers.UserDisplayName: Dude156
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-02T19:16:44.553Z
Answers.LastActivityDate: 2020-11-25T20:14:21.823Z
Answers.LastEditDate: 2020-11-25T20:14:21.823Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>In the policy gradient method, there's a trick to reduce the variance of policy gradient. We use causality, and remove part of the sum over rewards so that only actions happened after the reward are taken into account (See here <a href="http://rail.eecs.berkeley.edu/deeprlcourse/static/slides/lec-5.pdf" rel="noreferrer">http://rail.eecs.berkeley.edu/deeprlcourse/static/slides/lec-5.pdf</a>, slide 18).</p>
  <p>Why does it work? I understand the intuitive explanation, but what's the rigorous proof of it? Can you point me to some papers?</p>
  
Tags: <reinforcement-learning><math><policy-gradients><rewards><reward-to-go>
Title: Why does the "reward to go" trick in policy gradient methods work?
UserDisplayName: Konstantin Solomatov
ThreadText: # Why does the "reward to go" trick in policy gradient methods work?
  
  (Asked by: username_0 on 2018-12-20)
  
  In the policy gradient method, there's a trick to reduce the variance of policy gradient. We use causality, and remove part of the sum over rewards so that only actions happened after the reward are taken into account (See here <http://rail.eecs.berkeley.edu/deeprlcourse/static/slides/lec-5.pdf>, slide 18).
  
  Why does it work? I understand the intuitive explanation, but what's the rigorous proof of it? Can you point me to some papers?
  
  **Tags:** reinforcement-learning, math, policy-gradients, rewards, reward-to-go
  
  ---
  
  ## 3 answers
  
  ### Answer by username_3 on 2019-02-02. Score: 12 | Accepted answer
  
  An important thing we're going to need is what is called the ["Expected Grad-Log-Prob Lemma here"](https://spinningup.openai.com/en/latest/spinningup/rl_intro3.html#expected-grad-log-prob-lemma) (proof included on that page), which says that (for any $t$):
  
  $$\mathbb{E}\_{\tau \sim \pi\_{\theta}(\tau)} \left[ \nabla\_{\theta} \log \pi\_{\theta}(a\_t \mid s\_t) \right] = 0.$$
  
  Taking the analytical expression of the gradient (from, for example, slide 9) as a starting point:
  
  $$\begin{aligned}
  \nabla\_{\theta} J(\theta) &= \mathbb{E}\_{\tau \sim \pi\_{\theta}(\tau)} \left[ \left( \sum\_{t=1}^T \nabla\_{\theta} \log \pi\_{\theta} (a\_t \mid s\_t) \right) \left( \sum\_{t=1}^T r(s\_t, a\_t) \right) \right] \\
  %
  &= \sum\_{t=1}^T \mathbb{E}\_{\tau \sim \pi\_{\theta}(\tau)} \left[ \nabla\_{\theta} \log \pi\_{\theta} (a\_t \mid s\_t) \sum\_{t'=1}^T r(s\_{t'}, a\_{t'}) \right] \\
  %
  &= \sum\_{t=1}^T \mathbb{E}\_{\tau \sim \pi\_{\theta}(\tau)} \left[ \nabla\_{\theta} \log \pi\_{\theta} (a\_t \mid s\_t) \sum\_{t'=1}^{t-1} r(s\_{t'}, a\_{t'}) + \nabla\_{\theta} \log \pi\_{\theta} (a\_t \mid s\_t) \sum\_{t'=t}^T r(s\_{t'}, a\_{t'}) \right] \\
  %
  &= \sum\_{t=1}^T \left( \mathbb{E}\_{\tau \sim \pi\_{\theta}(\tau)} \left[ \nabla\_{\theta} \log \pi\_{\theta} (a\_t \mid s\_t) \sum\_{t'=1}^{t-1} r(s\_{t'}, a\_{t'}) \right] \\
  + \mathbb{E}\_{\tau \sim \pi\_{\theta}(\tau)} \left[ \nabla\_{\theta} \log \pi\_{\theta} (a\_t \mid s\_t) \sum\_{t'=t}^T r(s\_{t'}, a\_{t'}) \right] \right) \\
  \end{aligned}$$
  
  At the $t^{th}$ "iteration" of the outer sum, the random variables
  $ \sum\_{t'=1}^{t-1} r(s\_{t'}, a\_{t'}) $
  and
  $ \nabla\_{\theta} \log \pi\_{\theta} (a\_t \mid s\_t) $
  are independent (we assume, by definition, the action only depends on the most recent state), which means we are allowed to split the expectation:
  
  $$\nabla\_{\theta} J(\theta) = \sum\_{t=1}^T \left( \mathbb{E}\_{\tau \sim \pi\_{\theta}(\tau)} \left[ \sum\_{t'=1}^{t-1} r(s\_{t'}, a\_{t'}) \right] \mathbb{E}\_{\tau \sim \pi\_{\theta}(\tau)} \left[ \nabla\_{\theta} \log \pi\_{\theta} (a\_t \mid s\_t) \right] \\
  + \mathbb{E}\_{\tau \sim \pi\_{\theta}(\tau)} \left[ \nabla\_{\theta} \log \pi\_{\theta} (a\_t \mid s\_t) \sum\_{t'=t}^T r(s\_{t'}, a\_{t'}) \right] \right)$$
  
  The first expectation can now be replaced by $0$ due to the lemma mentioned at the top of the post:
  
  $$
  \begin{aligned}
  \nabla\_{\theta} J(\theta)
  %
  &= \sum\_{t=1}^T \mathbb{E}\_{\tau \sim \pi\_{\theta}(\tau)} \left[ \nabla\_{\theta} \log \pi\_{\theta} (a\_t \mid s\_t) \sum\_{t'=t}^T r(s\_{t'}, a\_{t'}) \right] \\
  %
  &= \mathbb{E}\_{\tau \sim \pi\_{\theta}(\tau)} \sum\_{t=1}^T \nabla\_{\theta} \log \pi\_{\theta} (a\_t \mid s\_t) \left( \sum\_{t'=t}^T r(s\_{t'}, a\_{t'}) \right). \\
  \end{aligned}
  $$
  
  The expression on slide 18 of the linked slides is an unbiased, sample-based estimator of this gradient:
  
  $$\nabla\_{\theta} J(\theta) \approx \frac{1}{N} \sum\_{i=1}^N \sum\_{t=1}^T \nabla\_{\theta} \log \pi\_{\theta} (a\_{i, t} \mid s\_{i, t}) \left( \sum\_{t'=t}^T r(s\_{i, t'}, a\_{i, t'}) \right)$$
  
  ---
  
  For a more formal treatment of the claim that we can pull $\sum\_{t'=1}^{t-1} r(s\_{t'}, a\_{t'})$ out of an expectation due to the Markov property, see this page: <https://spinningup.openai.com/en/latest/spinningup/extra_pg_proof1.html>
  
  > **Comments:**
  > **username_4**: Why is the form of "Expected Grad-Log-Prob Lemma" mentioned at the top of the post legit? It is different than the form of the proof shown in the link (the proof in the link has no problem). Your lemma is an expectation over **trajectories**.  
  > **username_3**: @starriet For the individual choice of a single action at one point in time within a trajectory, the trajectory as a whole has no influence (our policy does not look at the history or the future, just at the current state), so $\mathbb{E}_{\tau \sim \pi_{\theta}(\tau)} \left[ \nabla_{\theta} \log \pi_{\theta} (a_t \mid s_t) \right] = \mathbb{E}_{a_t \sim \pi_{\theta}} \left[ \nabla_{\theta} \log \pi_{\theta} (a_t \mid s_t) \right]$, where the right-hand side more closely matches that notation from the link.  
  > **username_3**: @starriet However, we use the trajectory-based notation because in the larger equation, we have these sums over all time steps, and that's the part where the full trajectory actually becomes relevant.  
  > **username_4**: Thanks, I think I got your point. If I understood correctly, the right-hand side is at a *specific state*, and the left-hand side is at the various states and actions of *all possible trajectories*, right? Since the RHS is 0 and it's about one state, LHS is also 0 because LHS is an expectation over all states (this is how I understood. please let me know if I'm wrong).  
  > **username_4**: But still, It's difficult to understand why the form of the LHS is legit. It's an expectation over trajectories, but the term inside of the square bracket is a function of action and state. Given that a trajectory is composed of many states and actions, how the expectation over trajectories is possible if the term inside of the brackets is smaller than a trajectory?  
  > **username_3**: @starriet Suppose that we have a "trajectory" $\tau$ where we roll 100 dice in a row. Forget about RL and actions and policies for a moment, just rolling 100 dice in a row. These dice rolls are independent of each other, so the expected value of any individual roll $x_t$ is $\mathbb{E}_{x_{t} \sim \text{dice-roll}} [ x_t ] = 3.5$. Here we take the expectation over just that single dice-roll event. We can also take it over the entire trajectory of all rolls though, but it won't change anything since they're independent: $\mathbb{E}_{\tau \sim \text{100 dice-rolls}} [ x_t ] = 3.5$.  
  > **username_3**: @starriet So here in RL with the actions it's kind of a similar idea. The expectation taken over the entire trajectory takes lots of extra irrelevant information into account which doesn't change anything due to independence (but it's convenient because we do need that "bigger" expectation elsewhere in the equation)  
  > **username_5**: This answer brought me closer to Enlightenment. Thanks Dennis.  
  
  ---
  
  ### Answer by username_1 on 2022-09-27. Score: 1
  
  A correct proof is given at <https://spinningup.openai.com/en/latest/spinningup/extra_pg_proof1.html>.
  It uses, among other techniques, the probability chain rule.
  
  On the contrary, an attempt to prove "reward to go" by applying
  $ X, Y \: independent \implies E[XY] = E[X]E[Y]$ does not work.
  
  The random variables
  $ \sum\_{t'=1}^{t-1} r(s\_{t'}, a\_{t'}) $
  and
  $ \nabla\_{\theta} \log \pi\_{\theta} (a\_t \mid s\_t) $
  are generally not independent.
  They would be independent, if
  $ P[ \nabla\_{\theta} \log \pi\_{\theta} (a\_t \mid s\_t) \mid \sum\_{t'=1}^{t-1} r(s\_{t'}, a\_{t'}) ] = P[ \nabla\_{\theta} \log \pi\_{\theta} (a\_t \mid s\_t) ] $ but this does not follow from
  $ \pi\_{\theta}(a\_t \mid s\_t) = \pi\_{\theta}(a\_t \mid s\_t, s\_{t-1},...,s\_1,a\_{t-1}, ..., a\_1) $
  
  Consider the following setup as an example for the dependency between the two random variables in question.
  
  times = {1, 2, 3, ..., T}
  
  states = {1, 2, 3, ..., T}
  
  actions = {0, 1}
  
  $ \pi(a\_t = 0 \mid s\_t) = \frac{1}{s\_t} $
  
  $ r(s\_t, a\_t) = 1 $
  i.e. the event reward at time t equals 1
  and the total reward from time 1 to time t-1 equals t-1
  
  $ P(s\_1 = 1) = 1 $
  i.e. all trajectories start in state 1
  
  $ P(s\_{t+1} = s\_t + 1 \mid s\_t, a\_t) = 1 $
  i.e. the next state, given the current state and the current action, is always the current state + 1
  
  As a result,
  the higher time $ t $,
  the higher the state $ s\_t $,
  the higher the probability for action $ a\_t = 1 $ and the higher the total reward from time $ 0 $ to time $ t-1 $,
  i.e. the values of $ \pi(a\_t \mid s\_t) $ and thus the values of $ \nabla\_{\theta} \log \pi (a\_t \mid s\_t) $
  are highly correlated with the total rewards from time $ 0 $ to time $ t-1 $,
  hence respective random variables are not independent of each other.
  
  
  ---
  
  ### Answer by username_2 on 2024-01-05. Score: 0
  
  By linearity of expection and using the distributive property:
  
  $$\begin{align} \nabla\_{\boldsymbol{\theta}} J(\boldsymbol{\theta}) &= \mathbb{E}\_{\tau \sim p\_{\boldsymbol{\theta}}(\tau)} \left[ \left( \sum\_{t=1}^T \nabla\_{\theta} \log \pi\_{\theta} (\mathbf{a}\_t \mid \mathbf{s}\_t) \right) \left( \sum\_{t=1}^T r(\mathbf{s}\_{t}, \mathbf{a}\_{t}) \right) \right] \\ &= \sum\_{t=1}^T \mathbb{E}\_{\tau \sim p\_{\boldsymbol{\theta}}(\tau)} \left[ \nabla\_{\theta} \log \pi\_{\boldsymbol{\theta}} (\mathbf{a}\_t \mid \mathbf{s}\_t) \sum\_{t'=1}^T r(\mathbf{s}\_{t'}, \mathbf{a}\_{t'}) \right] \\ &= \sum\_{t=1}^T \mathbb{E}\_{\tau \sim p\_{\boldsymbol{\theta}}(\tau)} \left[ \nabla\_{\theta} \log \pi\_{\boldsymbol{\theta}} (\mathbf{a}\_t \mid \mathbf{s}\_t) \sum\_{t'=1}^{t-1} r(\mathbf{s}\_{t'}, \mathbf{a}\_{t'}) +\nabla\_{\theta} \log \pi\_{\boldsymbol{\theta}} (\mathbf{a}\_t \mid \mathbf{s}\_t) \sum\_{t'=t}^T r(\mathbf{s}\_{t'}, \mathbf{a}\_{t'}) \right] \\ & = \sum\_{t=1}^T \sum\_{t'=1}^{t-1}\mathbb{E}\_{\tau \sim p\_{\boldsymbol{\theta}}(\tau)} \left[ \nabla\_{\boldsymbol{\theta}} \log \pi\_{\boldsymbol{\theta}} (\mathbf{a}\_t \mid \mathbf{s}\_t) \, r(\mathbf{s}\_{t'}, \mathbf{a}\_{t'}) \right] +\sum\_{t=1}^T \mathbb{E}\_{\tau \sim p\_{\boldsymbol{\theta}}(\tau)} \left[ \nabla\_{\boldsymbol{\theta}} \log \pi\_{\boldsymbol{\theta}} (\mathbf{a}\_t \mid \mathbf{s}\_t) \,\sum\_{t'=t}^T r(\mathbf{s}\_{t'}, \mathbf{a}\_{t'}) \right]\\ \end{align}$$
  
  and the first term can be further expanded as follows:
  
  $$\begin{align} &\sum\_{t=1}^T \sum\_{t'=1}^{t-1}\mathbb{E}\_{\tau \sim p\_{\boldsymbol{\theta}}(\tau)} \left[ \nabla\_{\boldsymbol{\theta}} \log \pi\_{\boldsymbol{\theta}} (\mathbf{a}\_t \mid \mathbf{s}\_t) \, r(\mathbf{s}\_{t'}, \mathbf{a}\_{t'}) \right] \\ = &\sum\_{t=1}^T \sum\_{t'=1}^{t-1} \mathbb{E}\_{(\mathbf{s}\_{t}, \mathbf{a}\_{t}, \mathbf{s}\_{t'}, \mathbf{a}\_{t'}) \sim p\_{\boldsymbol{\theta}}(\mathbf{s}\_{t}, \mathbf{a}\_{t}, \mathbf{s}\_{t'}, \mathbf{a}\_{t'})} \left[ \nabla\_{\boldsymbol{\theta}} \log \pi\_{\boldsymbol{\theta}} (\mathbf{a}\_t \mid \mathbf{s}\_t) \, r(\mathbf{s}\_{t'}, \mathbf{a}\_{t'}) \right] \\ = &\sum\_{t=1}^T \sum\_{t'=1}^{t-1} \mathbb{E}\_{(\mathbf{s}\_{t'}, \mathbf{a}\_{t'}) \sim p\_{\boldsymbol{\theta}}(\mathbf{s}\_{t'}, \mathbf{a}\_{t'})} \left[\mathbb{E}\_{(\mathbf{s}\_{t}, \mathbf{a}\_{t}) \sim p\_{\boldsymbol{\theta}}(\mathbf{s}\_{t}, \mathbf{a}\_{t} \mid \mathbf{s}\_{t'}, \mathbf{a}\_{t'})} \left[ \nabla\_{\boldsymbol{\theta}} \log \pi\_{\boldsymbol{\theta}} (\mathbf{a}\_t \mid \mathbf{s}\_t) \, r(\mathbf{s}\_{t'}, \mathbf{a}\_{t'}) \right] \right] \\ = &\sum\_{t=1}^T \sum\_{t'=1}^{t-1} \mathbb{E}\_{(\mathbf{s}\_{t'}, \mathbf{a}\_{t'}) \sim p\_{\boldsymbol{\theta}}(\mathbf{s}\_{t'}, \mathbf{a}\_{t'})} \left[ r(\mathbf{s}\_{t'}, \mathbf{a}\_{t'}) \; \mathbb{E}\_{(\mathbf{s}\_{t}, \mathbf{a}\_{t}) \sim p\_{\boldsymbol{\theta}}(\mathbf{s}\_{t}, \mathbf{a}\_{t} \mid \mathbf{s}\_{t'}, \mathbf{a}\_{t'})} \left[ \nabla\_{\boldsymbol{\theta}} \log \pi\_{\boldsymbol{\theta}} (\mathbf{a}\_t \mid \mathbf{s}\_t) \,\right] \right] \\ \end{align}
  $$
  
  The innermost expectation can be broken down further into
  $$\mathbb{E}\_{(\mathbf{s}\_{t}, \mathbf{a}\_{t}) \sim p\_{\boldsymbol{\theta}}(\mathbf{s}\_{t}, \mathbf{a}\_{t} \mid \mathbf{s}\_{t'}, \mathbf{a}\_{t'})} \left[ \nabla\_{\boldsymbol{\theta}} \log \pi\_{\boldsymbol{\theta}} (\mathbf{a}\_t \mid \mathbf{s}\_t) \right]\\ = \int \int \nabla\_{\boldsymbol{\theta}} \log \pi\_{\boldsymbol{\theta}} (\mathbf{a}\_t \mid \mathbf{s}\_t) \,\pi\_{\boldsymbol{\theta}}(\mathbf{a}\_t \mid \mathbf{s}\_t) \, \, p(\mathbf{s}\_{t} \mid \mathbf{s}\_{t'}, \mathbf{a}\_{t'})\, d\mathbf{a}\_t \; d \mathbf{s}\_t \\
  = \int p(\mathbf{s}\_{t} \mid \mathbf{s}\_{t'}, \mathbf{a}\_{t'}) \int \nabla\_{\boldsymbol{\theta}} \log \pi\_{\boldsymbol{\theta}} (\mathbf{a}\_t \mid \mathbf{s}\_t) \,\pi\_{\boldsymbol{\theta}}(\mathbf{a}\_t \mid \mathbf{s}\_t) \, d\mathbf{a}\_t \; d \mathbf{s}\_t$$
  
  where $ \int \nabla\_{\boldsymbol{\theta}} \log \pi\_{\boldsymbol{\theta}} (\mathbf{a}\_t \mid \mathbf{s}\_t) \,\pi\_{\boldsymbol{\theta}}(\mathbf{a}\_t \mid \mathbf{s}\_t) \, d\mathbf{a}\_t = \mathbb{E}\_{ \mathbf{a}\_{t} \sim \pi\_{\boldsymbol{\theta}}( \mathbf{a}\_{t} \mid \mathbf{s}\_{t})} \left[ \nabla\_{\boldsymbol{\theta}} \log \pi\_{\boldsymbol{\theta}} (\mathbf{a}\_t \mid \mathbf{s}\_t) \right] =0$ due to the [EGLP lemma](https://spinningup.openai.com/en/latest/spinningup/rl_intro3.html#expected-grad-log-prob-lemma)
  
  As a result, we have
  $$\nabla\_{\boldsymbol{\theta}} J(\boldsymbol{\theta}) = \sum\_{t=1}^T \mathbb{E}\_{\tau \sim p\_{\boldsymbol{\theta}}(\tau)} \left[ \nabla\_{\boldsymbol{\theta}} \log \pi\_{\boldsymbol{\theta}} (\mathbf{a}\_t \mid \mathbf{s}\_t) \,\sum\_{t'=t}^T r(\mathbf{s}\_{t'}, \mathbf{a}\_{t'}) \right]
  $$
  
  
  ---
  
  