Answers.Body: <p>If all states in an irreducible Markov chain (MC) are <a href="https://en.wikipedia.org/wiki/Markov_chain#Ergodicity" rel="nofollow noreferrer">ergodic</a>, then the chain is said to be ergodic. So once an ergodic MC is induced by a policy, then by above definition all states are irreducible. And irreducibility and communicating here are defined as:</p>
  <blockquote>
  <p>A Markov chain is irreducible if there is one communicating class, the state space.</p>
  </blockquote>
  <blockquote>
  <p>Two states are said to communicate with each other if both are reachable from one another by a sequence of transitions that have positive probability. This is an equivalence relation which yields a set of communicating classes.</p>
  </blockquote>
  <p>Since ergodicity implies irreducibility which means the existence of one communicating <em>class</em> as the whole state space, therefore any state is reachable from any other state within the said state space by following the said induced policy.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-21T08:18:39.120Z
Answers.Text: Are communicating and irreducible synonym then?
Answers.UserDisplayName: Simon
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-21T08:24:05.503Z
Answers.Text: @Simon not exactly. Communicating only refers to two states which is a more basic concept, while irreducibility is for the whole chain when there's only one communicating class for all states as emphasized in my above answer. And the concept of communicating class is resulted from an equivalence relation of communicating states in the sense of set theory which is also mentioned in my answer. So if there's only one communicating class for all the states of a chain, then it implies all states are mutually communicating with each other. Hope this clarifies.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-18T06:12:45.950Z
Answers.LastActivityDate: 2024-11-18T06:12:45.950Z
Answers.UserDisplayName: cinch
Answers.Body: <p>There are inconsistencies in the definition of an <a href="https://math.stackexchange.com/questions/152491/is-ergodic-markov-chain-both-irreducible-and-aperiodic-or-just-irreducible">ergodic Markov Chain</a> while de concepts of irreducibility, aperiodicity and recurrence are well grounded.</p>
  <p>Thus, I think it is better not to employ this term too much and keep the word &quot;ergodic&quot; for the well-known theorem.</p>
  <p>According to the paper you cite,</p>
  <blockquote>
  <p>An MDP is ergodic if the
  Markov chain induced by any policy π is both irreducible
  and aperiodic, which means any state is reachable from
  any other state by following a suitable policy.</p>
  </blockquote>
  <p>So what can we say about that?
  Let <span class="math-container">$\mathcal{X}$</span> be the state space.</p>
  <p>If the chain is irreducible, then whether all states are recurrent, or all states are transient.
  But if <span class="math-container">$dim(\mathcal{X}) &lt; \infty$</span>, then the second case is impossible.</p>
  <p>Thus if the chain is irreducible and <span class="math-container">$dim(\mathcal{X}) &lt; \infty$</span>, then the chain is recurrent.</p>
  <p>Now, If the chain is irreducible and recurrent, there exists a unique (up to a normalisation factor) stationary measure <span class="math-container">$\mu$</span>.</p>
  <p>Also, if the chain is recurrent, irreducible and aperiodic, then there is a <span class="math-container">$n_0$</span> such that for any <span class="math-container">$n&gt;n_0$</span>, <span class="math-container">$P_n(x, y) &gt; 0$</span> for any states <span class="math-container">$x, y \in \mathcal{X}$</span>, where <span class="math-container">$P_n$</span> is the <span class="math-container">$n$</span> steps transition probability kernel. This means any state <span class="math-container">$x \in \mathcal{X}$</span> is reachable from any other state <span class="math-container">$y \in \mathcal{X}$</span>.</p>
  <p>Sources: [1]</p>
  <p>[1]: J-F. Le Gall - Intégration, Probabilités et Processus Aléatoires (2006)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-19T18:16:03.103Z
Answers.LastActivityDate: 2024-11-25T21:57:38.787Z
Answers.LastEditDate: 2024-11-25T21:57:38.787Z
Answers.UserDisplayName: Rémy Hosseinkhan Boucher
Body: <blockquote>
  <p>An MDP is ergodic if the Markov chain induced by any policy is
  ergodic, which means any state is reachable from any other state by
  following a suitable policy. <a href="https://proceedings.mlr.press/v130/hao21b/hao21b.pdf" rel="nofollow noreferrer">[Source]</a></p>
  </blockquote>
  <p>The part after &quot;which means ...&quot; is the definition of communicating MDP. Why does &quot;the Markov chain induced by any policy is ergodic&quot; implies &quot;any state is reachable from any other state by following a suitable policy&quot;?</p>
  <p>Other papers/books define an ergodic MDP just with &quot;if the Markov chain induced by any policy is ergodic&quot;, but they all say that an ergodic MDP is also communicating. Why ergodic → communicating?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-11-17T14:40:52.083Z
Comments.Text: _Why does it hold?_ what? nothing has to hold, they are defining what is an ergodic MDP
Comments.UserDisplayName: Alberto
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-11-17T18:06:46.410Z
Comments.Text: Why does "the Markov chain induced by any policy is ergodic" implies "any state is reachable from any other state by following a suitable policy"?  @Alberto
Comments.UserDisplayName: Simon
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-11-17T20:59:26.443Z
Comments.Text: it's not an implication, it is a definition "MDP is ergodic $\rightarrow$ any state is reachable from any other state by following a suitable policy"
Comments.UserDisplayName: Alberto
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-11-17T23:50:54.957Z
Comments.Text: @Alberto Then what is the difference with communicating MDP? "Any state is reachable from any other state by following a suitable policy" is the definition of communicating MDP. Also, Puterman's book defines ergodic MDP just with "if the Markov chain induced by any policy is ergodic", then saying that communicating MDPs are also ergodic (thus, the implication I don't understand).
Comments.UserDisplayName: Simon
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-11-17T23:59:41.617Z
Comments.Text: i think that the communicating case is "there exists a policy that can move from state $i$ to state $j$ in a finite set of steps", while for ergodic MDP "state $i$ can be reached by state $j$ under any stationary policy", so it's a much stronger assumption
Comments.UserDisplayName: Alberto
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-11-18T00:12:25.840Z
Comments.Text: @Alberto I think "any" is not right. Ergodic means 1) that there exists **A** policy that "connects" every two states (communicating) + 2) every policy induces an ergodic Markov chain. But not that **EVERY** policy does it (unichain MDPs do that for EVERY policy). Anyway, my question is that all definitions seem to imply that 1) is implied from 2) and it's not part of the definition.
Comments.UserDisplayName: Simon
Tags: <papers><definitions><markov-decision-process><markov-chain><ergodicity>
Title: Why are ergodic MDPs also communicating?
UserDisplayName: Simon
ThreadText: # Why are ergodic MDPs also communicating?
  
  (Asked by: username_0 on 2024-11-17)
  
  > An MDP is ergodic if the Markov chain induced by any policy is
  > ergodic, which means any state is reachable from any other state by
  > following a suitable policy. [[Source]](https://proceedings.mlr.press/v130/hao21b/hao21b.pdf)
  
  The part after "which means ..." is the definition of communicating MDP. Why does "the Markov chain induced by any policy is ergodic" implies "any state is reachable from any other state by following a suitable policy"?
  
  Other papers/books define an ergodic MDP just with "if the Markov chain induced by any policy is ergodic", but they all say that an ergodic MDP is also communicating. Why ergodic → communicating?
  
  **Tags:** papers, definitions, markov-decision-process, markov-chain, ergodicity
  
  > **Comments:**
  > **username_1**: _Why does it hold?_ what? nothing has to hold, they are defining what is an ergodic MDP  
  > **username_0**: Why does "the Markov chain induced by any policy is ergodic" implies "any state is reachable from any other state by following a suitable policy"?  @username_1  
  > **username_1**: it's not an implication, it is a definition "MDP is ergodic $\rightarrow$ any state is reachable from any other state by following a suitable policy"  
  > **username_0**: @username_1 Then what is the difference with communicating MDP? "Any state is reachable from any other state by following a suitable policy" is the definition of communicating MDP. Also, Puterman's book defines ergodic MDP just with "if the Markov chain induced by any policy is ergodic", then saying that communicating MDPs are also ergodic (thus, the implication I don't understand).  
  > **username_1**: i think that the communicating case is "there exists a policy that can move from state $i$ to state $j$ in a finite set of steps", while for ergodic MDP "state $i$ can be reached by state $j$ under any stationary policy", so it's a much stronger assumption  
  > **username_0**: @username_1 I think "any" is not right. Ergodic means 1) that there exists **A** policy that "connects" every two states (communicating) + 2) every policy induces an ergodic Markov chain. But not that **EVERY** policy does it (unichain MDPs do that for EVERY policy). Anyway, my question is that all definitions seem to imply that 1) is implied from 2) and it's not part of the definition.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2024-11-18. Score: 2 | Accepted answer
  
  If all states in an irreducible Markov chain (MC) are [ergodic](https://en.wikipedia.org/wiki/Markov_chain#Ergodicity), then the chain is said to be ergodic. So once an ergodic MC is induced by a policy, then by above definition all states are irreducible. And irreducibility and communicating here are defined as:
  
  > A Markov chain is irreducible if there is one communicating class, the state space.
  
  > Two states are said to communicate with each other if both are reachable from one another by a sequence of transitions that have positive probability. This is an equivalence relation which yields a set of communicating classes.
  
  Since ergodicity implies irreducibility which means the existence of one communicating *class* as the whole state space, therefore any state is reachable from any other state within the said state space by following the said induced policy.
  
  > **Comments:**
  > **username_0**: Are communicating and irreducible synonym then?  
  > **username_2**: @username_0 not exactly. Communicating only refers to two states which is a more basic concept, while irreducibility is for the whole chain when there's only one communicating class for all states as emphasized in my above answer. And the concept of communicating class is resulted from an equivalence relation of communicating states in the sense of set theory which is also mentioned in my answer. So if there's only one communicating class for all the states of a chain, then it implies all states are mutually communicating with each other. Hope this clarifies.  
  
  ---
  
  ### Answer by username_3 on 2024-11-19. Score: 2
  
  There are inconsistencies in the definition of an [ergodic Markov Chain](https://math.stackexchange.com/questions/152491/is-ergodic-markov-chain-both-irreducible-and-aperiodic-or-just-irreducible) while de concepts of irreducibility, aperiodicity and recurrence are well grounded.
  
  Thus, I think it is better not to employ this term too much and keep the word "ergodic" for the well-known theorem.
  
  According to the paper you cite,
  
  > An MDP is ergodic if the
  > Markov chain induced by any policy π is both irreducible
  > and aperiodic, which means any state is reachable from
  > any other state by following a suitable policy.
  
  So what can we say about that?
  Let $\mathcal{X}$ be the state space.
  
  If the chain is irreducible, then whether all states are recurrent, or all states are transient.
  But if $dim(\mathcal{X}) < \infty$, then the second case is impossible.
  
  Thus if the chain is irreducible and $dim(\mathcal{X}) < \infty$, then the chain is recurrent.
  
  Now, If the chain is irreducible and recurrent, there exists a unique (up to a normalisation factor) stationary measure $\mu$.
  
  Also, if the chain is recurrent, irreducible and aperiodic, then there is a $n\_0$ such that for any $n>n\_0$, $P\_n(x, y) > 0$ for any states $x, y \in \mathcal{X}$, where $P\_n$ is the $n$ steps transition probability kernel. This means any state $x \in \mathcal{X}$ is reachable from any other state $y \in \mathcal{X}$.
  
  Sources: [1]
  
  [1]: J-F. Le Gall - Intégration, Probabilités et Processus Aléatoires (2006)
  
  
  ---
  
  