Stationary Distribution of a Markov Decision Process

The stationary distribution of $S$ under policy $\pi$ can bedenoted by ${\{d_{\pi }(s)\}}_{s\in \mathcal{S}}$. By definition, $d_{\pi }(s)\ge 0$ and $\sum _{s\in \mathcal{S}}{d}_{\pi }(s)=1$.

Let $n_{\pi }(s)$ denote the number of times that $s$ has been visited in a very ong episode generated by $\pi$. Then, $d_{\pi }(s)$ can be approximated by $$d_{\pi }(s)\approx \frac{n_{\pi }(s)}{\sum _{s^{\prime }\in \mathcal{S}}{n}_{\pi }\left(s^{\prime }\right)}$$ Meanwhile, the converged values $d_{\pi }(s)$ can be computed directly by solving equation: $$d_{\pi }^T=d_{\pi }^T{P}_{\pi },$$ i.e., $d_{\pi }$ is the left eigenvector of $P_{\pi }$ associated with the eigenvalue 1.

Sources:

1. Shiyu Zhao. Chapter 8: Value Function Approximation. Mathematical Foundations of Reinforcement Learning.

Interpretation of $P_{\pi }^k(k=1,2,3,\dots )$

The key tool for analyzing stationary distribution is $P_{\pi }\in {\mathbb{R}}^{n\times n}$, which is the probability transition matrix under the given policy $\pi$.

If the states are indexed as $s_1,\dots ,s_n$, then ${\left[P_{\pi }\right]}_{ij}$ is defined as the probability for the agent moving from $s_i$ to $s_j$. The probability of the agent transitioning from $s_i$ to $s_j$ using exactly $k$ steps is denoted as $$p_{ij}^{(k)}=\mathrm{Pr}(S_{t_k}=j\mid S_{t_0}=i),$$ where $t_0$ and $t_k$ are the initial and $k$ th time steps, respectively. First, by the definition of $P_{\pi }$, we have $${\left[P_{\pi }\right]}_{ij}=p_{ij}^{(1)},$$ which means that ${\left[P_{\pi }\right]}_{ij}$ is the probability of transitioning from $s_i$ to $s_j$ using $a$ single step. Second, consider $P_{\pi }^2$. It can be verified that $${\left[P_{\pi }^2\right]}_{ij}={\left[P_{\pi }{P}_{\pi }\right]}_{ij}=\sum _{q=1}^n{\left[P_{\pi }\right]}_{iq}{\left[P_{\pi }\right]}_{qj}.$$

Since ${\left[P_{\pi }\right]}_{iq}{\left[P_{\pi }\right]}_{qj}$ is the joint probability of transitioning from $s_i$ to $s_q$ and then from $s_q$ to $s_j$, we know that ${\left[P_{\pi }^2\right]}_{ij}$ is the probability of transitioning from $s_i$ to $s_j$ using exactly two steps. That is $${\left[P_{\pi }^2\right]}_{ij}=p_{ij}^{(2)}$$

Similarly, we know that $${\left[P_{\pi }^k\right]}_{ij}=p_{ij}^{(k)}$$ which means that ${\left[P_{\pi }^k\right]}_{ij}$ is the probability of transitioning from $s_i$ to $s_j$ using exactly $k$ steps.

Definition of stationary distributions.

Let $d_0\in {\mathbb{R}}^n$ be a vector representing the probability distribution of the states at the initial time step. For example, if $s$ is always selected as the starting state, then $d_0(s)=1$ and the other entries of $d_0$ are 0 . Let $d_k\in {\mathbb{R}}^n$ be the vector representing the probability distribution obtained after exactly $k$ steps starting from $d_0$. Then, we have $$d_k\left(s_i\right)=\sum _{j=1}^n{d}_0\left(s_j\right){\left[P_{\pi }^k\right]}_{ji},i=1,2,\dots$$

This equation indicates that the probability of the agent visiting $s_i$ at step $k$ equals the sum of the probabilities of the agent transitioning from ${\left\{s_j\right\}}_{j=1}^n$ to $s_i$ using exactly $k$ steps. The matrix-vector form of the last equation is $$\begin{array}{}\text{(1)}& d_k^T=d_0^T{P}_{\pi }^k.\end{array}$$

When we consider the long-term behavior of the Markov process, it holds under certain conditions that $$\begin{array}{}\text{(2)}& \underset{k\to \mathrm{\infty }}{lim}{P}_{\pi }^k={\mathbf{1}}_n{d}_{\pi }^T,\end{array}$$ where ${\mathbf{1}}_n=[1,\dots ,1{]}^T\in {\mathbb{R}}^n$ and ${\mathbf{1}}_n{d}_{\pi }^T$ is a constant matrix with all its rows equal to $d_{\pi }^T$. The conditions under which $\text{(2)}$ is valid will be discussed later. Substituting $\text{(2)}$ into $\text{(1)}$ yields $$\underset{k\to \mathrm{\infty }}{lim}{d}_k^T=d_0^T\underset{k\to \mathrm{\infty }}{lim}{P}_{\pi }^k=d_0^T{\mathbf{1}}_n{d}_{\pi }^T=d_{\pi }^T,$$ where the last equality is valid because $d_0^T{\mathbf{1}}_n=1$.

The last equation means that the state distribution $d_k$ converges to a constant value $d_{\pi }$, which is called the limiting distribution.

The limiting distribution depends on the system model and the policy $\pi$. Interestingly, it is independent of the initial distribution $d_0$. That is, regardless of which state the agent starts from, the probability distribution of the agent after a sufficiently long period can always be described by the limiting distribution.

The value of $d_{\pi }$ can be calculated in the following way. Taking the limit of both sides of $d_k^T=d_{k-1}^T{P}_{\pi }$¹ gives $$\underset{k\to \mathrm{\infty }}{lim}{d}_k^T=\underset{k\to \mathrm{\infty }}{lim}{d}_{k-1}^T{P}_{\pi }$$ and hence $$\begin{array}{}\text{(3)}& d_{\pi }^T=d_{\pi }^T{P}_{\pi }\end{array}$$

As a result, $d_{\pi }$ is the left eigenvector of $P_{\pi }$ associated with the eigenvalue 1. The solution of ($\text{(3)}$) is called the stationary distribution. It holds that $\sum _{s\in \mathcal{S}}{d}_{\pi }(s)=$ 1 and $d_{\pi }(s)>0$ for all $s\in \mathcal{S}$. The reason why $d_{\pi }(s)>0$ (not $d_{\pi }(s)\ge 0$ ) will be explained later (#TODO).

---

1. This is because $d_k^T=d_0^T{P}_{\pi }^k$.↩︎