Answers.Body: <p>Besides stationary policy whose decision at each state doesn't depend on time in a MDP context, the <a href="https://en.wikipedia.org/wiki/Markov_chain#Ergodicity" rel="nofollow noreferrer">ergodic criterion</a> for the policy-induced Markov chain (MC) is <em>irreducibility</em> of the said chain and <em>aperiodicity</em> and <em>positive recurrence</em> of <em>all</em> states.</p>
  <blockquote>
  <p>If all states in an irreducible Markov chain are ergodic, then the chain is said to be ergodic.</p>
  </blockquote>
  <blockquote>
  <p>A Markov chain is irreducible if there is one communicating class, the state space.</p>
  </blockquote>
  <blockquote>
  <p>A state <span class="math-container">$i$</span> is said to be ergodic if it is aperiodic and positive recurrent. In other words, a state <span class="math-container">$i$</span> is ergodic if it is recurrent, has a period of <span class="math-container">$1$</span>, and has finite mean recurrence time.</p>
  </blockquote>
  <p>Once these 3 conditions are met, the induced MC must have a stationary distribution due to its ergodicity. A prime example is ideal gas in statistical mechanics following the famous <a href="https://en.wikipedia.org/wiki/Maxwell%E2%80%93Boltzmann_distribution" rel="nofollow noreferrer">Maxwell-Boltzmann distribution</a>.</p>
  <hr />
  <p>Edit per OP's addition and clarification:</p>
  <p>If you only want a stationary distribution, subtly you may not need a ergodic induced MC as clearly illustrated with this <a href="https://en.wikipedia.org/wiki/Markov_chain#Time-homogeneous_Markov_chain_with_a_finite_state_space" rel="nofollow noreferrer">simple example in the above same reference</a>.</p>
  <blockquote>
  <p>For some stochastic matrices P, the limit <span class="math-container">${\textstyle \lim _{k\to \infty }\mathbf {P} ^{k}}$</span> does not exist while the stationary distribution does, as shown by this example:
  <span class="math-container">$${\displaystyle \mathbf {P} ={\begin{pmatrix}0&amp;1\\1&amp;0\end{pmatrix}}\qquad \mathbf {P} ^{2k}=I\qquad \mathbf {P} ^{2k+1}=\mathbf {P} }$$</span> <span class="math-container">$${\displaystyle {\begin{pmatrix}{\frac {1}{2}}&amp;{\frac {1}{2}}\end{pmatrix}}{\begin{pmatrix}0&amp;1\\1&amp;0\end{pmatrix}}={\begin{pmatrix}{\frac {1}{2}}&amp;{\frac {1}{2}}\end{pmatrix}}}$$</span>
  (This example illustrates a periodic Markov chain.)</p>
  </blockquote>
  <p>Since the environment transition matrix or kernel <span class="math-container">$P$</span> is always a <a href="https://en.wikipedia.org/wiki/Stochastic_matrix" rel="nofollow noreferrer">stochastic matrix</a>, the (not necessarily unique) existence of a stationary distribution is always guaranteed if every entry <span class="math-container">$P_{i,j}$</span> is positive ensuring irreducibility. Of course if the <span class="math-container">$P$</span> is further aperiodic with mean positive recurrence to become ergodic, such existence is unique per Perron-Frobenius theorem.</p>
  <blockquote>
  <p>Intuitively, a stochastic matrix represents a Markov chain; the application of the stochastic matrix to a probability distribution redistributes the probability mass of the original distribution while preserving its total mass. If this process is applied repeatedly, the distribution converges to a stationary distribution for the Markov chain.</p>
  </blockquote>
  <p>As for policies, those ensure sufficient exploration (e.g., ϵ-greedy or stochastic policies) promote irreducibility by enabling transitions to all parts of the state space. If a policy ignores certain states such as deterministic policies DPG without appropriate noise added (e.g., Ornstein–Uhlenbeck or Gaussian noise), it can create disconnected components in the chain, violating irreducibility and failing to ensure positive recurrence.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-19T17:36:26.630Z
Answers.Text: I understand that we need these conditions. What I meant with my question is if there is a condition on the policy and the transition function that tell us if the Markov chain is positive. For example, if the transition matrix under the policy is positive semi-definite, has eigenvalues of a certain type, ... (I am just making things up, but I am looking for conditions like that).
Answers.UserDisplayName: Simon
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-19T20:59:05.933Z
Answers.Text: I've expanded my answer to address your added scope of concerns, hope it clarifies.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-21T00:02:28.803Z
Answers.Text: Great thanks! This is what I was looking for. It would be great maybe to have more info or refs on what "P is further aperiodic with mean positive recurrence", but I can Google that :)
Answers.UserDisplayName: Simon
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-18T07:27:17.480Z
Answers.LastActivityDate: 2024-11-19T21:04:05.760Z
Answers.LastEditDate: 2024-11-19T21:04:05.760Z
Answers.UserDisplayName: cinch
Body: <p>If the Markov chain induced by the policy is ergodic, then the state distribution under the policy is stationary.</p>
  <p>Are there some conditions/properties (sufficient or necessary, on the MDP or on the policy) to check if a policy induces an ergodic Markov chain? (Beside stationary transition and stationary policy).
  That is, can we say if the Markov chain induced by the policy is stationary by looking at the resulting transition matrix <span class="math-container">$P_{ss'}^\pi = \sum_a P(s'|s,a)\pi(a|s)$</span>? For example, maybe if the eigenvector of this matrix are all positive, or some other condition like that.</p>
  
Tags: <markov-decision-process>
Title: Conditions for the existence of stationary state distribution
UserDisplayName: Simon
ThreadText: # Conditions for the existence of stationary state distribution
  
  (Asked by: username_0 on 2024-11-18)
  
  If the Markov chain induced by the policy is ergodic, then the state distribution under the policy is stationary.
  
  Are there some conditions/properties (sufficient or necessary, on the MDP or on the policy) to check if a policy induces an ergodic Markov chain? (Beside stationary transition and stationary policy).
  That is, can we say if the Markov chain induced by the policy is stationary by looking at the resulting transition matrix $P\_{ss'}^\pi = \sum\_a P(s'|s,a)\pi(a|s)$? For example, maybe if the eigenvector of this matrix are all positive, or some other condition like that.
  
  **Tags:** markov-decision-process
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-11-18. Score: 1 | Accepted answer
  
  Besides stationary policy whose decision at each state doesn't depend on time in a MDP context, the [ergodic criterion](https://en.wikipedia.org/wiki/Markov_chain#Ergodicity) for the policy-induced Markov chain (MC) is *irreducibility* of the said chain and *aperiodicity* and *positive recurrence* of *all* states.
  
  > If all states in an irreducible Markov chain are ergodic, then the chain is said to be ergodic.
  
  > A Markov chain is irreducible if there is one communicating class, the state space.
  
  > A state $i$ is said to be ergodic if it is aperiodic and positive recurrent. In other words, a state $i$ is ergodic if it is recurrent, has a period of $1$, and has finite mean recurrence time.
  
  Once these 3 conditions are met, the induced MC must have a stationary distribution due to its ergodicity. A prime example is ideal gas in statistical mechanics following the famous [Maxwell-Boltzmann distribution](https://en.wikipedia.org/wiki/Maxwell%E2%80%93Boltzmann_distribution).
  
  ---
  
  Edit per OP's addition and clarification:
  
  If you only want a stationary distribution, subtly you may not need a ergodic induced MC as clearly illustrated with this [simple example in the above same reference](https://en.wikipedia.org/wiki/Markov_chain#Time-homogeneous_Markov_chain_with_a_finite_state_space).
  
  > For some stochastic matrices P, the limit ${\textstyle \lim \_{k\to \infty }\mathbf {P} ^{k}}$ does not exist while the stationary distribution does, as shown by this example:
  > $${\displaystyle \mathbf {P} ={\begin{pmatrix}0&1\\1&0\end{pmatrix}}\qquad \mathbf {P} ^{2k}=I\qquad \mathbf {P} ^{2k+1}=\mathbf {P} }$$ $${\displaystyle {\begin{pmatrix}{\frac {1}{2}}&{\frac {1}{2}}\end{pmatrix}}{\begin{pmatrix}0&1\\1&0\end{pmatrix}}={\begin{pmatrix}{\frac {1}{2}}&{\frac {1}{2}}\end{pmatrix}}}$$
  > (This example illustrates a periodic Markov chain.)
  
  Since the environment transition matrix or kernel $P$ is always a [stochastic matrix](https://en.wikipedia.org/wiki/Stochastic_matrix), the (not necessarily unique) existence of a stationary distribution is always guaranteed if every entry $P\_{i,j}$ is positive ensuring irreducibility. Of course if the $P$ is further aperiodic with mean positive recurrence to become ergodic, such existence is unique per Perron-Frobenius theorem.
  
  > Intuitively, a stochastic matrix represents a Markov chain; the application of the stochastic matrix to a probability distribution redistributes the probability mass of the original distribution while preserving its total mass. If this process is applied repeatedly, the distribution converges to a stationary distribution for the Markov chain.
  
  As for policies, those ensure sufficient exploration (e.g., ϵ-greedy or stochastic policies) promote irreducibility by enabling transitions to all parts of the state space. If a policy ignores certain states such as deterministic policies DPG without appropriate noise added (e.g., Ornstein–Uhlenbeck or Gaussian noise), it can create disconnected components in the chain, violating irreducibility and failing to ensure positive recurrence.
  
  > **Comments:**
  > **username_0**: I understand that we need these conditions. What I meant with my question is if there is a condition on the policy and the transition function that tell us if the Markov chain is positive. For example, if the transition matrix under the policy is positive semi-definite, has eigenvalues of a certain type, ... (I am just making things up, but I am looking for conditions like that).  
  > **username_1**: I've expanded my answer to address your added scope of concerns, hope it clarifies.  
  > **username_0**: Great thanks! This is what I was looking for. It would be great maybe to have more info or refs on what "P is further aperiodic with mean positive recurrence", but I can Google that :)  
  
  ---
  
  