Answers.Body: <p>The expectation of a sum is equal to the sum of the expectation this just follows from the linearity property of expectations</p>
  <p><span class="math-container">$$ \begin{aligned} E[\sum_{t} f(s_t,a_t)] &amp;= \sum_{\tau} p(\tau)\left(\sum_t f(s_t,a_t)\right)
   \\ &amp;= \sum_\tau\sum_{t}p(\tau)f(s_t,a_t) 
   \\ &amp;= \sum_t\sum_\tau p(\tau)f(s_{t,\tau},a_{t,\tau}) 
   \\ &amp;= \sum_tE[f(s_t,a_t)]
  \end{aligned} $$</span></p>
  <p>note that in the penultimate line I swapped the sums around which can be understood as looking at all trajectories for a single time-step instead of looking at time-steps within  a single trajectory (the second expression). I append subscript for variables in the penultimate line for clarity since they also depend on which trajectory they were drawn from.</p>
  <hr />
  <p>As mentioned by nboro in the comments, the linearity of property only holds for infinite sums if</p>
  <p><span class="math-container">$$\sum_{i=0}^\infty E[|X|]&lt; \infty  \quad or \quad E\left[\sum_{i=0}^{\infty}|X|\right]. &lt;\infty$$</span></p>
  <p>More details can be found <a href="https://math.stackexchange.com/questions/1166994/linearity-of-expectation-for-infinite-sums">here</a>. Using this theory alongside knowledge that since we know that value functions in RL are always bounded (in continuing tasks discounting factors are introduced) then we can say there exists an <span class="math-container">$M$</span> such that</p>
  <p><span class="math-container">$$ |f(s_{t,\tau},a_{t,\tau})| \leq M \qquad \forall t,\tau $$</span></p>
  <p>Then</p>
  <p><span class="math-container">$$ \begin{aligned}\sum_t\sum_\tau \lambda^t p(\tau)|f(s_{t,\tau},a_{t,\tau})| &amp;\leq \sum_t\sum_\tau \lambda^t p(\tau)M 
  \\ &amp;=M\sum_t\lambda^t\sum p(\tau)
  \\ &amp;=M\sum\lambda^t
  \\ &amp;&lt; \infty
  \end{aligned}$$</span></p>
  <p>As for the rest of the proof is there anything else you need clarity on? it looks good to me. From that step to the next step where you change distribution from <span class="math-container">$p(\tau)$</span> to <span class="math-container">$p(s,a)$</span> is just because of marginalisation but I think you got that.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-29T20:43:38.603Z
Answers.Text: This may explain the first step of the derivation, but what about the other steps? Moreover, maybe you should clarify **if** or **when** the linearity of the expectation also applies when you have an infinite sum, as it is the case. Maybe take a look at https://math.stackexchange.com/q/575974/168764.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-29T19:46:30.450Z
Answers.LastActivityDate: 2021-01-29T22:09:45.093Z
Answers.LastEditDate: 2021-01-29T22:09:45.093Z
Answers.UserDisplayName: quest ions
Body: <p>In Sham Kakade's <em><a href="https://rltheorybook.github.io/rltheorybook_AJKS.pdf" rel="nofollow noreferrer">Reinforcement Learning: Theory and Algorithms</a></em>, this equation (page 17) is used preceding the proof of performance difference lemma.</p>
  <p><a href="https://i.sstatic.net/s78YR.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/s78YR.png" alt="enter image description here" /></a></p>
  <p>I am attempting to prove equation 0.6. Here is my current attempt:</p>
  <p><span class="math-container">\begin{align*}
          \mathbb{E}_{\tau \sim \rho^\pi}\left[\sum\limits_{t=0}^\infty \gamma^t f(s_t,a_t)\right] &amp;= \sum\limits_{t=0}^\infty \gamma^t \mathbb{E}_{\tau \sim \rho^\pi} [f(s_t,a_t)]\\
          &amp;= \sum\limits_{t=0}^\infty \gamma^t \mathbb{E}_{s_t, a_t} [f(s_t,a_t)]\\
          &amp;= \sum\limits_{t=0}^\infty \gamma^t \sum\limits_{s, a} \mathbb{P}(s_t = s, a_t = a) f(s,a)\\
          &amp;= \sum\limits_{t=0}^\infty \gamma^t \sum\limits_{s} \mathbb{P}(s_t = s) \sum\limits_{a}\pi(a_t = a|s_t = s) f(s,a)\\
          &amp;= \frac{1 - \gamma}{1 - \gamma}\sum\limits_{t=0}^\infty \gamma^t \sum\limits_{s} \mathbb{P}(s_t = s) \mathbb{E}_{a \sim \pi(s)} [f(s,a)]\\
          &amp;= \frac{1}{1 - \gamma} \sum\limits_{s} (1-\gamma) \sum\limits_{t=0}^\infty \gamma^t \mathbb{P}(s_t = s) \mathbb{E}_{a \sim \pi(s)} [f(s,a)]\\
          &amp;=\frac{1}{(1-\gamma)} \mathbb{E}_{s \sim d^\pi}\left[\mathbb{E}_{a \sim \pi(s)}\left[f(s,a)\right]\right] \\
  \end{align*}</span></p>
  <p>Is the swapping of expectation and summation in this way allowed (given that the series converges)?</p>
  <p>Note that this is not the proof of the performance difference lemma, but just an attempt to show equation 0.6, which is used but not proved in the book.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-09-12T06:16:11.510Z
Comments.Text: Hi, late question, but why is the seond equalitys valid in your proof? Specifically why we can switch from trajectory to state-acton notation
Comments.UserDisplayName: craaaft
Tags: <reinforcement-learning><proofs>
Title: Is my proof of equation 0.6 in the book "Reinforcement Learning: Theory and Algorithms" correct?
UserDisplayName: Isomorphism
ThreadText: # Is my proof of equation 0.6 in the book "Reinforcement Learning: Theory and Algorithms" correct?
  
  (Asked by: username_0 on 2021-01-28)
  
  In Sham Kakade's *[Reinforcement Learning: Theory and Algorithms](https://rltheorybook.github.io/rltheorybook_AJKS.pdf)*, this equation (page 17) is used preceding the proof of performance difference lemma.
  
  [![enter image description here](https://i.sstatic.net/s78YR.png)](https://i.sstatic.net/s78YR.png)
  
  I am attempting to prove equation 0.6. Here is my current attempt:
  
  \begin{align\*}
  \mathbb{E}\_{\tau \sim \rho^\pi}\left[\sum\limits\_{t=0}^\infty \gamma^t f(s\_t,a\_t)\right] &= \sum\limits\_{t=0}^\infty \gamma^t \mathbb{E}\_{\tau \sim \rho^\pi} [f(s\_t,a\_t)]\\
  &= \sum\limits\_{t=0}^\infty \gamma^t \mathbb{E}\_{s\_t, a\_t} [f(s\_t,a\_t)]\\
  &= \sum\limits\_{t=0}^\infty \gamma^t \sum\limits\_{s, a} \mathbb{P}(s\_t = s, a\_t = a) f(s,a)\\
  &= \sum\limits\_{t=0}^\infty \gamma^t \sum\limits\_{s} \mathbb{P}(s\_t = s) \sum\limits\_{a}\pi(a\_t = a|s\_t = s) f(s,a)\\
  &= \frac{1 - \gamma}{1 - \gamma}\sum\limits\_{t=0}^\infty \gamma^t \sum\limits\_{s} \mathbb{P}(s\_t = s) \mathbb{E}\_{a \sim \pi(s)} [f(s,a)]\\
  &= \frac{1}{1 - \gamma} \sum\limits\_{s} (1-\gamma) \sum\limits\_{t=0}^\infty \gamma^t \mathbb{P}(s\_t = s) \mathbb{E}\_{a \sim \pi(s)} [f(s,a)]\\
  &=\frac{1}{(1-\gamma)} \mathbb{E}\_{s \sim d^\pi}\left[\mathbb{E}\_{a \sim \pi(s)}\left[f(s,a)\right]\right] \\
  \end{align\*}
  
  Is the swapping of expectation and summation in this way allowed (given that the series converges)?
  
  Note that this is not the proof of the performance difference lemma, but just an attempt to show equation 0.6, which is used but not proved in the book.
  
  **Tags:** reinforcement-learning, proofs
  
  > **Comments:**
  > **username_1**: Hi, late question, but why is the seond equalitys valid in your proof? Specifically why we can switch from trajectory to state-acton notation  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-01-29. Score: 1 | Accepted answer
  
  The expectation of a sum is equal to the sum of the expectation this just follows from the linearity property of expectations
  
  $$ \begin{aligned} E[\sum\_{t} f(s\_t,a\_t)] &= \sum\_{\tau} p(\tau)\left(\sum\_t f(s\_t,a\_t)\right)
  \\ &= \sum\_\tau\sum\_{t}p(\tau)f(s\_t,a\_t)
  \\ &= \sum\_t\sum\_\tau p(\tau)f(s\_{t,\tau},a\_{t,\tau})
  \\ &= \sum\_tE[f(s\_t,a\_t)]
  \end{aligned} $$
  
  note that in the penultimate line I swapped the sums around which can be understood as looking at all trajectories for a single time-step instead of looking at time-steps within a single trajectory (the second expression). I append subscript for variables in the penultimate line for clarity since they also depend on which trajectory they were drawn from.
  
  ---
  
  As mentioned by nboro in the comments, the linearity of property only holds for infinite sums if
  
  $$\sum\_{i=0}^\infty E[|X|]< \infty \quad or \quad E\left[\sum\_{i=0}^{\infty}|X|\right]. <\infty$$
  
  More details can be found [here](https://math.stackexchange.com/username_2/1166994/linearity-of-expectation-for-infinite-sums). Using this theory alongside knowledge that since we know that value functions in RL are always bounded (in continuing tasks discounting factors are introduced) then we can say there exists an $M$ such that
  
  $$ |f(s\_{t,\tau},a\_{t,\tau})| \leq M \qquad \forall t,\tau $$
  
  Then
  
  $$ \begin{aligned}\sum\_t\sum\_\tau \lambda^t p(\tau)|f(s\_{t,\tau},a\_{t,\tau})| &\leq \sum\_t\sum\_\tau \lambda^t p(\tau)M
  \\ &=M\sum\_t\lambda^t\sum p(\tau)
  \\ &=M\sum\lambda^t
  \\ &< \infty
  \end{aligned}$$
  
  As for the rest of the proof is there anything else you need clarity on? it looks good to me. From that step to the next step where you change distribution from $p(\tau)$ to $p(s,a)$ is just because of marginalisation but I think you got that.
  
  > **Comments:**
  > **username_3**: This may explain the first step of the derivation, but what about the other steps? Moreover, maybe you should clarify **if** or **when** the linearity of the expectation also applies when you have an infinite sum, as it is the case. Maybe take a look at https://math.stackexchange.com/q/575974/168764.  
  
  ---
  
  