1
$\begingroup$

I was reading the original Policy Gradient Paper. 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

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ $\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. $\endgroup$
    – David Ireland
    Aug 7, 2022 at 20:54
  • $\begingroup$ @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? $\endgroup$
    – Fady
    Aug 8, 2022 at 14:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – David Ireland
    Aug 8, 2022 at 15:16

1 Answer 1

Reset to default
3
$\begingroup$

This sum is not equal to the stationary distribution actually. Rigorously, it should be

$$\sum_{k=0}^\infty \gamma^k \mathrm{Pr}(s_0\rightarrow s,k,\pi)= \left[(I_n-\gamma P_{\pi})^{-1}\right]_{s_0s}=\mathrm{Pr}_{\pi}(s|s_0)\doteq\rho_\pi(s)$$ which can be called the total discounted state transition probability. Here, $P_\pi$ is the state transition matrix.

Moreover, people usually do not care about whether $\rho_\pi$ is the same as $d_\pi$. That is because $\rho_\pi$ is also a distribution similar to the stationary distribution that describes long-run behaviors of the underlying Markov process given the policy. When we write the gradient in terms of expectation or we use the stochastic policy gradient, the distribution will disappear.

If you are really interested, you can check Chapter~9 of this book Mathematical Foundation of Reinforcement Learning for details. In particular, you can check Theorem 9.2 for details of the above equation. You will also see that if we want to calculate the rigorous policy gradients, we need to be careful about different objective functions and discounted/undiscounted cases.

Hope it is helpful.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .