Answers.Body: <p>I think your doubt is completely reasonable. Probably there is an additional assumption that they (both Lilian Weng and <a href="http://incompleteideas.net/book/bookdraft2017nov5.pdf" rel="nofollow noreferrer">Rich Sutton</a> (pag.269)) do not make explicit in the proof and that is that your MDP is not only stationary, but also <strong>ergodic</strong>. A particular property of those systems is that the probability of eventually reaching a state <span class="math-container">$s$</span> from a starting point <span class="math-container">$s_0$</span> is 1. In such a case it is clear that <span class="math-container">$\eta(s)$</span> exists and is independent of any <span class="math-container">$s_0$</span> chosen. </p>
  
  <p>Clearly, an MDP with block-diagonal transition matrix does not satisfy such an assumption since the starting point completely restricts those states you can reach in an infinite time.</p>
  
  <p>What I do not understand is why Rich Sutton does mention ergodicity as a necessary condition in the case of a "continuing task", as opposed to "episodic tasks" (pag.275). For me, their proof requires this condition in both cases.</p>
  
  <p>As an additional note, I also think that Lilian Weng does not really explain why we should buy that from the initial reasonable definition <span class="math-container">$J(\theta)=\sum_\mathcal S d^{\pi_\theta}(s)V^{\pi_\theta}(s)$</span> we should accept the much simpler one <span class="math-container">$J(\theta)=V^{\pi_\theta}(s_0)$</span>. I guess the only reason is that the gradient of the initial expression does require to know the gradient of <span class="math-container">$d^{\pi_\theta}(s)$</span> and so you would be accepting the approximation:</p>
  
  <p><span class="math-container">$$\nabla_\theta J(\theta)=\nabla_\theta\left(\sum_\mathcal S d^{\pi_\theta}(s)V^{\pi_\theta}(s)\right)\approx\sum_\mathcal S d^{\pi_\theta}(s)\nabla_\theta V^{\pi_\theta}(s),$$</span></p>
  
  <p>where the last term is just <span class="math-container">$\nabla_\theta V^{\pi_\theta}(s_0)$</span> under the ergodicity assumption. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-04T23:15:31.457Z
Answers.Text: Yes, the second part you mentioned left me also a bit confused. I don't quite see why $\sum d^\pi (s) V^\pi (s) = V^\pi (s_0) $ should be true, even if the system is ergodic. Generally, $V^\pi(s_0)$ makes more sense to me since in practice we always start from $s_0$ and don't sample $s_0$ from $d^\pi (s)$.
Answers.UserDisplayName: Luca Thiede
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-04T23:31:57.130Z
Answers.Text: I'm not really saying that the expected value of $V^{\pi}(s)$ is $V^\pi(s_0)$. What is true (if the system is ergodic) is that the expected value of $\nabla V^{\pi}(s)$ is $ \nabla V^\pi(s_0)$, given that the gradient is the same for all states since $\eta(s)$ does not depend on $s_0$.
Answers.UserDisplayName: Diego Gomez
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-04T23:32:49.063Z
Answers.Text: About what performance metric is better, I consider that usually you want your policy to be robust, so you not only want to consider one single $s_0$. What happens then if by some perturbance your agent is forced to start in a different state? At least you should consider an initial distribution $\rho(s_0)$. This is done in the TRPO paper, for example.
Answers.UserDisplayName: Diego Gomez
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-04T22:32:52.290Z
Answers.LastActivityDate: 2019-12-04T22:32:52.290Z
Answers.UserDisplayName: Diego Gomez
Body: <p>I was going through the proof of the policy gradient theorem here: <a href="https://lilianweng.github.io/lil-log/2018/04/08/policy-gradient-algorithms.html#svpg" rel="nofollow noreferrer">https://lilianweng.github.io/lil-log/2018/04/08/policy-gradient-algorithms.html#svpg</a> </p>
  
  <p>In the section "Proof of Policy Gradient Theorem" in the block of equations just under the sentence "The nice rewriting above allows us to exclude the derivative of Q-value function..." they set
  <span class="math-container">$$
  \eta (s) = \sum^\infty_{k=0} \rho^\pi(s_0 \rightarrow s, k)
  $$</span>
  and
  <span class="math-container">$$
  \sum_s \eta (s) = const
  $$</span>
  Thus, they basically assume, that the stationary distribution is not dependent on the initial state. But how can we justify this? If the MDP is described by a block diagonal transition matrix, in my mind this should not hold.</p>
  
Tags: <reinforcement-learning><policy-gradients><proofs><policy-gradient-theorem>
Title: Why is the stationary distribution independent of the initial state in the proof of the policy gradient theorem?
UserDisplayName: Luca Thiede
ThreadText: # Why is the stationary distribution independent of the initial state in the proof of the policy gradient theorem?
  
  (Asked by: username_0 on 2019-12-03)
  
  I was going through the proof of the policy gradient theorem here: <https://lilianweng.github.io/lil-log/2018/04/08/policy-gradient-algorithms.html#svpg>
  
  In the section "Proof of Policy Gradient Theorem" in the block of equations just under the sentence "The nice rewriting above allows us to exclude the derivative of Q-value function..." they set
  $$
  \eta (s) = \sum^\infty\_{k=0} \rho^\pi(s\_0 \rightarrow s, k)
  $$
  and
  $$
  \sum\_s \eta (s) = const
  $$
  Thus, they basically assume, that the stationary distribution is not dependent on the initial state. But how can we justify this? If the MDP is described by a block diagonal transition matrix, in my mind this should not hold.
  
  **Tags:** reinforcement-learning, policy-gradients, proofs, policy-gradient-theorem
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-12-04. Score: 1 | Accepted answer
  
  I think your doubt is completely reasonable. Probably there is an additional assumption that they (both Lilian Weng and [Rich Sutton](http://incompleteideas.net/book/bookdraft2017nov5.pdf) (pag.269)) do not make explicit in the proof and that is that your MDP is not only stationary, but also **ergodic**. A particular property of those systems is that the probability of eventually reaching a state $s$ from a starting point $s\_0$ is 1. In such a case it is clear that $\eta(s)$ exists and is independent of any $s\_0$ chosen.
  
  Clearly, an MDP with block-diagonal transition matrix does not satisfy such an assumption since the starting point completely restricts those states you can reach in an infinite time.
  
  What I do not understand is why Rich Sutton does mention ergodicity as a necessary condition in the case of a "continuing task", as opposed to "episodic tasks" (pag.275). For me, their proof requires this condition in both cases.
  
  As an additional note, I also think that Lilian Weng does not really explain why we should buy that from the initial reasonable definition $J(\theta)=\sum\_\mathcal S d^{\pi\_\theta}(s)V^{\pi\_\theta}(s)$ we should accept the much simpler one $J(\theta)=V^{\pi\_\theta}(s\_0)$. I guess the only reason is that the gradient of the initial expression does require to know the gradient of $d^{\pi\_\theta}(s)$ and so you would be accepting the approximation:
  
  $$\nabla\_\theta J(\theta)=\nabla\_\theta\left(\sum\_\mathcal S d^{\pi\_\theta}(s)V^{\pi\_\theta}(s)\right)\approx\sum\_\mathcal S d^{\pi\_\theta}(s)\nabla\_\theta V^{\pi\_\theta}(s),$$
  
  where the last term is just $\nabla\_\theta V^{\pi\_\theta}(s\_0)$ under the ergodicity assumption.
  
  > **Comments:**
  > **username_0**: Yes, the second part you mentioned left me also a bit confused. I don't quite see why $\sum d^\pi (s) V^\pi (s) = V^\pi (s_0) $ should be true, even if the system is ergodic. Generally, $V^\pi(s_0)$ makes more sense to me since in practice we always start from $s_0$ and don't sample $s_0$ from $d^\pi (s)$.  
  > **username_1**: I'm not really saying that the expected value of $V^{\pi}(s)$ is $V^\pi(s_0)$. What is true (if the system is ergodic) is that the expected value of $\nabla V^{\pi}(s)$ is $ \nabla V^\pi(s_0)$, given that the gradient is the same for all states since $\eta(s)$ does not depend on $s_0$.  
  > **username_1**: About what performance metric is better, I consider that usually you want your policy to be robust, so you not only want to consider one single $s_0$. What happens then if by some perturbance your agent is forced to start in a different state? At least you should consider an initial distribution $\rho(s_0)$. This is done in the TRPO paper, for example.  
  
  ---
  
  