Body: <p>I was reading the original <a href="https://proceedings.neurips.cc/paper/1999/file/464d828b85b0bed98e80ade0a5c43b0f-Paper.pdf" rel="nofollow noreferrer">Policy Gradient Paper</a>. I didn't quiet get the last step of the proof for the policy gradient theorem. The proof given in the paper is below:
  <a href="https://i.sstatic.net/JPMoY.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/JPMoY.png" alt="enter image description here" /></a></p>
  <p>I don't understand how the last line follows from the second to last line. That is how is the following true? <span class="math-container">$d^\pi(s) = \sum_{k=0}^{\infty}\gamma^{k}Pr(s_0 \rightarrow s, k, \pi)$</span>
  where <span class="math-container">$d^\pi$</span> is the stationary distribution of the MDP with fixed policy <span class="math-container">$\pi$</span> and <span class="math-container">$Pr(s_0 \rightarrow s, k, \pi)$</span> is probability of transitioning from state <span class="math-container">$s_0$</span> to state <span class="math-container">$s$</span> in exactly <span class="math-container">$k$</span> timesteps.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-08-07T20:54:34.057Z
Comments.Text: $\sum_{k=0}^\infty \mathbb{P}(s_0 \rightarrow s, k, \pi)$ is equivalent to the steady state distribution $d^\pi (s)$ if we assume that the MDP is ergodic. You can see this because due to ergodicity, in the limit $k \rightarrow \infty$, the state visitation distribution becomes independent of time (this is loosely speaking the definition of ergodicity) and so this is the state distribution. Intuitively, it is saying that because the MDP is ergodic, independent of whatever we do at the start of the MDP we will eventually reach this 'steady state' distribution.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-08-08T14:05:55.913Z
Comments.Text: @DavidIreland I don't quite get it. I would have thought given the MDP is ergodic that $d_\pi(s)=lim_{k \to \infty} Pr(s_0 \rightarrow s, k, \pi)$ as this is the definition of steady state probabilities. Also using the infinite sum, $d_\pi(s_0)$ would be more than 1 because  $Pr(s_0 \rightarrow s_0, 0, \pi) = 1$ and as the MDP is ergodic, there is some probability of self transition back to $s_0$ after some finite number of timesteps, so $d_\pi(s)$ therefore would not be a valid probability distribution right?
Comments.UserDisplayName: Fady
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-08-08T15:16:11.313Z
Comments.Text: Yes you are right about that -- I do believe in the paper they mention it is the _improper_ state distribution, i.e. it has not been normalised. I'm fairly certain they mention it there, or in the Sutton & Barto book. I should note that $d$ is also the _discounted_ state distribution.
Comments.UserDisplayName: David
Tags: <reinforcement-learning><markov-decision-process><policy-gradients><policy-gradient-theorem>
Title: In the Policy Gradient Theorem proof, why is $d^\pi(s) = \sum_{k=0}^{\infty}\gamma^{k}Pr(s_0 \rightarrow s, k, \pi)$ true?
UserDisplayName: Fady
ThreadText: # In the Policy Gradient Theorem proof, why is $d^\pi(s) = \sum_{k=0}^{\infty}\gamma^{k}Pr(s_0 \rightarrow s, k, \pi)$ true?
  
  (Asked by: username_0 on 2022-08-07)
  
  I was reading the original [Policy Gradient Paper](https://proceedings.neurips.cc/paper/1999/file/464d828b85b0bed98e80ade0a5c43b0f-Paper.pdf). I didn't quiet get the last step of the proof for the policy gradient theorem. The proof given in the paper is below:
  [![enter image description here](https://i.sstatic.net/JPMoY.png)](https://i.sstatic.net/JPMoY.png)
  
  I don't understand how the last line follows from the second to last line. That is how is the following true? $d^\pi(s) = \sum\_{k=0}^{\infty}\gamma^{k}Pr(s\_0 \rightarrow s, k, \pi)$
  where $d^\pi$ is the stationary distribution of the MDP with fixed policy $\pi$ and $Pr(s\_0 \rightarrow s, k, \pi)$ is probability of transitioning from state $s\_0$ to state $s$ in exactly $k$ timesteps.
  
  **Tags:** reinforcement-learning, markov-decision-process, policy-gradients, policy-gradient-theorem
  > **Comments:**
  > **username_1**: $\sum_{k=0}^\infty \mathbb{P}(s_0 \rightarrow s, k, \pi)$ is equivalent to the steady state distribution $d^\pi (s)$ if we assume that the MDP is ergodic. You can see this because due to ergodicity, in the limit $k \rightarrow \infty$, the state visitation distribution becomes independent of time (this is loosely speaking the definition of ergodicity) and so this is the state distribution. Intuitively, it is saying that because the MDP is ergodic, independent of whatever we do at the start of the MDP we will eventually reach this 'steady state' distribution.  
  > **username_0**: @DavidIreland I don't quite get it. I would have thought given the MDP is ergodic that $d_\pi(s)=lim_{k \to \infty} Pr(s_0 \rightarrow s, k, \pi)$ as this is the definition of steady state probabilities. Also using the infinite sum, $d_\pi(s_0)$ would be more than 1 because  $Pr(s_0 \rightarrow s_0, 0, \pi) = 1$ and as the MDP is ergodic, there is some probability of self transition back to $s_0$ after some finite number of timesteps, so $d_\pi(s)$ therefore would not be a valid probability distribution right?  
  > **username_1**: Yes you are right about that -- I do believe in the paper they mention it is the _improper_ state distribution, i.e. it has not been normalised. I'm fairly certain they mention it there, or in the Sutton & Barto book. I should note that $d$ is also the _discounted_ state distribution.  
  
  ---
  
  ## 0 answers
  
  