Answers.Body: <p>In short, the relevant class of a MDPs that guarantees the existence of a unique stationary state distribution for every deterministic stationary policy are <em>unichain MDPs</em> (Puterman 1994, Sect. 8.3). However, the unichain assumption does <strong>not</strong> mean that every policy will eventually visit every state. I believe your confusion arises from the difference between unichain and more constrained ergodic MDPs.</p>
  <p>Puterman defines that a MDP is (emphasis in the following mine):</p>
  <blockquote>
  <ul>
  <li>recurrent or ergodic if the state transition matrix corresponding to every deterministic stationary policy consists of a single recurrent
  class, and</li>
  <li>unichain, if the state transition matrix corresponding to every deterministic stationary policy is unichain, that is, it consists of a
  single recurrent class <strong>and a possibly empty set of transient states</strong>.</li>
  </ul>
  </blockquote>
  <p>Before unpacking this further, let's first recap what recurrent and transient states in a Markov chain are. The following definitions can be found in Puterman, Appendix A.2. For a state <span class="math-container">$s$</span>, associate two random variables <span class="math-container">$\nu_s$</span> and <span class="math-container">$\tau_s$</span> that represent the number of visits and the time of the first visit (or first return if the chain starts in <span class="math-container">$s$</span>) to state <span class="math-container">$s$</span>. A state <span class="math-container">$s$</span> is</p>
  <ul>
  <li>recurrent (sometimes also called ergodic), if <span class="math-container">$P_s(\tau_s &lt; \infty) = 1$</span>, that is, the state is eventually visited (or returned to), and</li>
  <li>transient, if <span class="math-container">$\mathbb{E}[\tau_s] = \infty$</span> and <span class="math-container">$P_s(\tau_s &lt; \infty) &lt; 1$</span>.</li>
  </ul>
  <p>It is also true that <span class="math-container">$s$</span> is recurrent if and only if <span class="math-container">$\mathbb{E}[\nu_s] = \infty$</span>, i.e., it is visited infinitely often, and <span class="math-container">$s$</span> is transient if and only if <span class="math-container">$\mathbb{E}[\nu_s] &lt; \infty$</span>, i.e., it is visited only finitely often (and thereby never again after some finite time).</p>
  <p>So let's now return to the two types of MDPs above. Consider an arbitrary deterministic stationary policy <span class="math-container">$\pi$</span> which maps any state <span class="math-container">$s$</span> to an action <span class="math-container">$a = \pi(s)$</span>. If the MDP is ergodic, then the stationary distribution <span class="math-container">$\mu_\pi(s)$</span> exists and is unique, because the Markov chain over states induced by any policy has a single recurrent class (it does not matter in which state <span class="math-container">$s_0$</span> the chain starts, the same stationary distribution is reached). There is a single class of recurrent states, i.e., all states are recurrent, therefore any <span class="math-container">$s$</span> is visited infinitely often and <span class="math-container">$\mu_\pi(s) &gt; 0$</span>.</p>
  <p>Now, if the MDP is unichain, then once again the stationary distribution <span class="math-container">$\mu_\pi(s)$</span> exists and is unique, because the Markov chain over states induced by any policy has a single recurrent class. But, importantly, there may exist a policy <span class="math-container">$\pi$</span> for which the set of transient states in the induced Markov chain is not empty. Because any transient state <span class="math-container">$s$</span> will only be visited a finite number of times, in the (infinite horizon) stationary distribution <span class="math-container">$\mu_\pi(s)=0$</span>!</p>
  <p>So indeed, if the MDP is of the stricter ergodic type, every policy will eventually visit every state. This is not true for unichain MDPs however.</p>
  <p>A final remark: some authors define a <em>policy</em> as ergodic (e.g., Kearns &amp; Singh, 2002), if the resulting Markov chain over states is ergodic (i.e., has a unique stationary distribution). The unichain MDP is a type of MDP where every policy is ergodic.</p>
  <p><strong>References:</strong></p>
  <p>Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming.</p>
  <p>Kearns &amp; Singh. Near-Optimal Reinforcement Learning in Polynomial Time. Machine Learning, 49, 209–232, 2002</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-12T11:09:03.140Z
Answers.Text: From what I gathered, I have misunderstood what the second definition of ergodicity in my post (the one from Sutton) implied. It does **not** imply that "there is a chance of landing on state $s$ by executing actions according to policy $\pi$". Only that when following a policy $\pi$, the probability of visiting a state $\mu_\pi$ is "fixed", i.e., the only thing that changes the probability of visiting a state is the policy $\pi$. I wrongly assumed that ergodicity meant $\mu_\pi(s) > 0, \forall s \in S$, as some states may have $\mu_\pi(s) = 0$ (like unichain MDPs).
Answers.UserDisplayName: josealeixo.pc
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-12T11:17:28.043Z
Answers.Text: But then, I still don't understand if there's a definitive definition for ergodicity. In this thread there are 3 different definitions. (1): there exists a policy $\pi$ such that $\mu_\pi(s) > 0, \forall s \in S$ - the one from Moldovan; (2): for every policy $\pi$, and for all states $\mu_\pi(s)$ exists (and may be equal to 0) - the one from Sutton; (3): for every policy $\pi$, $\mu_\pi(s) > 0, \forall s \in S$ -  the one from Puterman. Should I just clarify what I mean by "ergodicity" when I refer to it, given this ambiguity?
Answers.UserDisplayName: josealeixo.pc
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-12T13:36:10.063Z
Answers.Text: Certainly makes sense to clarify which definition you use. The Moldovan definition concerns something other than ergodicity of MDPs, namely "beliefs over MDPs" in their language. For that I have no comments to add. Sutton (2) is a bit vague, and seems like they could mean something that either equals Puterman's ergodic OR unichain case. All this shows that ergodicity in a MDP is context dependent, could be a property of the MDP as a whole, or a policy, or something even different. Puterman is the authoritative source on MDP theory, and I find he gives very clear defintions of the fundamentals.
Answers.UserDisplayName: mikkola
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-12T13:54:15.627Z
Answers.Text: I was unaware of the Puterman book. I'll certainly look into reading it. I have considered your answer as correct, as you provided a formal definition of ergodicity in an MDP. Given that I have always associated ergodicity with being able to eventually visit any state $s'$ from any other state $s$, I will probably be using Puterman's definition in the context of MDPs and Moldovan's in the context of policies. Thank you very much!
Answers.UserDisplayName: josealeixo.pc
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-10T11:26:28.787Z
Answers.LastActivityDate: 2021-04-10T11:55:10.507Z
Answers.LastEditDate: 2021-04-10T11:55:10.507Z
Answers.UserDisplayName: mikkola
Body: <p>I have read about the concept of <strong>ergodicity</strong> on the <a href="https://arxiv.org/abs/1205.4810" rel="nofollow noreferrer">safe RL paper by Moldovan (section 3.2)</a> and the <a href="http://incompleteideas.net/book/the-book.html" rel="nofollow noreferrer">RL book by Sutton (chapter 10.3, 2nd paragraph)</a>.</p>
  <p>The first one says that &quot;a belief over MDPs is ergodic if and only if any state is reachable from any other state via some policy or, equivalently, if and only if&quot;:</p>
  <p><span class="math-container">$$\forall s, s', \exists \pi_r \text{ such that } E_\beta E_{s, \pi_r}^P [B_{s'}] = 1$$</span></p>
  <p>where:</p>
  <ul>
  <li><span class="math-container">$B_{s'}$</span> is an indicator random variable of the event that the system reaches state <span class="math-container">$s'$</span> at least once, i.e., <span class="math-container">$B_{s'} = 1 \{ \exists t &lt; \infty \text{ such that } s_t = s'\}$</span></li>
  <li><span class="math-container">$E_\beta E_{s, \pi_r}^P[B_{s'}]$</span> is the expected value for <span class="math-container">$B_{s'}$</span>, under the belief over the MDP dynamics <span class="math-container">$\beta$</span>, policy <span class="math-container">$\pi$</span> and transition measure <span class="math-container">$P$</span>.</li>
  </ul>
  <p>The second one says &quot;<span class="math-container">$\mu_\pi$</span> is the steady-state distribution, which is assumed to exist for any <span class="math-container">$\pi$</span> and to be independent of <span class="math-container">$s_0$</span>. This assumption about the MDP is known as ergodicity.&quot;. They define <span class="math-container">$\mu_\pi$</span> as:</p>
  <p><span class="math-container">$$\mu_\pi(s) \doteq \lim_{t \to \infty} \Pr\{s_t=s \vert a_{0:t-1} \sim \pi\}$$</span></p>
  <ul>
  <li>i.e., there is a chance of landing on state <span class="math-container">$s$</span> by executing actions according to policy <span class="math-container">$\pi$</span>.</li>
  </ul>
  <p>I noticed that the first definition requires that <strong>at least one</strong> policy should exist for each <span class="math-container">$(s, s')$</span> pair for the MDP to be ergodic The second definition, however, requires that <strong>all policies</strong> eventually visit all the states in an MDP, which seems to be a more strict definition.</p>
  <p>Then, I came accross the ergodicity definition for Markov chains:</p>
  <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. If all states in an irreducible Markov chain are ergodic, then the chain is said to be ergodic.</p>
  </blockquote>
  <p>This leads me to believe that the second definition (the stricter one) is the most appropriate one, considering the ergodicity definition in an MDP derives from the definition in a Markov chain. As an MDP is basically a Markov chain with choice (actions), ergodicity should mean that independently of the action taken, all states are visited, i.e., <strong>all policies</strong> ensure ergodicity.</p>
  <p>Am I correct in assuming these are different definitions? Can both still be called &quot;ergodicity&quot;? If not, which one is the most correct?</p>
  
Tags: <reinforcement-learning><definitions><markov-decision-process><markov-chain><ergodicity>
Title: What is ergodicity in a Markov Decision Process (MDP)?
UserDisplayName: josealeixo.pc
ThreadText: # What is ergodicity in a Markov Decision Process (MDP)?
  
  (Asked by: username_0 on 2021-04-07)
  
  I have read about the concept of **ergodicity** on the [safe RL paper by Moldovan (section 3.2)](https://arxiv.org/abs/1205.4810) and the [RL book by Sutton (chapter 10.3, 2nd paragraph)](http://incompleteideas.net/book/the-book.html).
  
  The first one says that "a belief over MDPs is ergodic if and only if any state is reachable from any other state via some policy or, equivalently, if and only if":
  
  $$\forall s, s', \exists \pi\_r \text{ such that } E\_\beta E\_{s, \pi\_r}^P [B\_{s'}] = 1$$
  
  where:
  
  * $B\_{s'}$ is an indicator random variable of the event that the system reaches state $s'$ at least once, i.e., $B\_{s'} = 1 \{ \exists t < \infty \text{ such that } s\_t = s'\}$
  * $E\_\beta E\_{s, \pi\_r}^P[B\_{s'}]$ is the expected value for $B\_{s'}$, under the belief over the MDP dynamics $\beta$, policy $\pi$ and transition measure $P$.
  
  The second one says "$\mu\_\pi$ is the steady-state distribution, which is assumed to exist for any $\pi$ and to be independent of $s\_0$. This assumption about the MDP is known as ergodicity.". They define $\mu\_\pi$ as:
  
  $$\mu\_\pi(s) \doteq \lim\_{t \to \infty} \Pr\{s\_t=s \vert a\_{0:t-1} \sim \pi\}$$
  
  * i.e., there is a chance of landing on state $s$ by executing actions according to policy $\pi$.
  
  I noticed that the first definition requires that **at least one** policy should exist for each $(s, s')$ pair for the MDP to be ergodic The second definition, however, requires that **all policies** eventually visit all the states in an MDP, which seems to be a more strict definition.
  
  Then, I came accross the ergodicity definition for Markov chains:
  
  > 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. If all states in an irreducible Markov chain are ergodic, then the chain is said to be ergodic.
  
  This leads me to believe that the second definition (the stricter one) is the most appropriate one, considering the ergodicity definition in an MDP derives from the definition in a Markov chain. As an MDP is basically a Markov chain with choice (actions), ergodicity should mean that independently of the action taken, all states are visited, i.e., **all policies** ensure ergodicity.
  
  Am I correct in assuming these are different definitions? Can both still be called "ergodicity"? If not, which one is the most correct?
  
  **Tags:** reinforcement-learning, definitions, markov-decision-process, markov-chain, ergodicity
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-04-10. Score: 7 | Accepted answer
  
  In short, the relevant class of a MDPs that guarantees the existence of a unique stationary state distribution for every deterministic stationary policy are *unichain MDPs* (Puterman 1994, Sect. 8.3). However, the unichain assumption does **not** mean that every policy will eventually visit every state. I believe your confusion arises from the difference between unichain and more constrained ergodic MDPs.
  
  Puterman defines that a MDP is (emphasis in the following mine):
  
  > * recurrent or ergodic if the state transition matrix corresponding to every deterministic stationary policy consists of a single recurrent
  >   class, and
  > * unichain, if the state transition matrix corresponding to every deterministic stationary policy is unichain, that is, it consists of a
  >   single recurrent class **and a possibly empty set of transient states**.
  
  Before unpacking this further, let's first recap what recurrent and transient states in a Markov chain are. The following definitions can be found in Puterman, Appendix A.2. For a state $s$, associate two random variables $\nu\_s$ and $\tau\_s$ that represent the number of visits and the time of the first visit (or first return if the chain starts in $s$) to state $s$. A state $s$ is
  
  * recurrent (sometimes also called ergodic), if $P\_s(\tau\_s < \infty) = 1$, that is, the state is eventually visited (or returned to), and
  * transient, if $\mathbb{E}[\tau\_s] = \infty$ and $P\_s(\tau\_s < \infty) < 1$.
  
  It is also true that $s$ is recurrent if and only if $\mathbb{E}[\nu\_s] = \infty$, i.e., it is visited infinitely often, and $s$ is transient if and only if $\mathbb{E}[\nu\_s] < \infty$, i.e., it is visited only finitely often (and thereby never again after some finite time).
  
  So let's now return to the two types of MDPs above. Consider an arbitrary deterministic stationary policy $\pi$ which maps any state $s$ to an action $a = \pi(s)$. If the MDP is ergodic, then the stationary distribution $\mu\_\pi(s)$ exists and is unique, because the Markov chain over states induced by any policy has a single recurrent class (it does not matter in which state $s\_0$ the chain starts, the same stationary distribution is reached). There is a single class of recurrent states, i.e., all states are recurrent, therefore any $s$ is visited infinitely often and $\mu\_\pi(s) > 0$.
  
  Now, if the MDP is unichain, then once again the stationary distribution $\mu\_\pi(s)$ exists and is unique, because the Markov chain over states induced by any policy has a single recurrent class. But, importantly, there may exist a policy $\pi$ for which the set of transient states in the induced Markov chain is not empty. Because any transient state $s$ will only be visited a finite number of times, in the (infinite horizon) stationary distribution $\mu\_\pi(s)=0$!
  
  So indeed, if the MDP is of the stricter ergodic type, every policy will eventually visit every state. This is not true for unichain MDPs however.
  
  A final remark: some authors define a *policy* as ergodic (e.g., Kearns & Singh, 2002), if the resulting Markov chain over states is ergodic (i.e., has a unique stationary distribution). The unichain MDP is a type of MDP where every policy is ergodic.
  
  **References:**
  
  Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming.
  
  Kearns & Singh. Near-Optimal Reinforcement Learning in Polynomial Time. Machine Learning, 49, 209–232, 2002
  
  > **Comments:**
  > **username_0**: From what I gathered, I have misunderstood what the second definition of ergodicity in my post (the one from Sutton) implied. It does **not** imply that "there is a chance of landing on state $s$ by executing actions according to policy $\pi$". Only that when following a policy $\pi$, the probability of visiting a state $\mu_\pi$ is "fixed", i.e., the only thing that changes the probability of visiting a state is the policy $\pi$. I wrongly assumed that ergodicity meant $\mu_\pi(s) > 0, \forall s \in S$, as some states may have $\mu_\pi(s) = 0$ (like unichain MDPs).  
  > **username_0**: But then, I still don't understand if there's a definitive definition for ergodicity. In this thread there are 3 different definitions. (1): there exists a policy $\pi$ such that $\mu_\pi(s) > 0, \forall s \in S$ - the one from Moldovan; (2): for every policy $\pi$, and for all states $\mu_\pi(s)$ exists (and may be equal to 0) - the one from Sutton; (3): for every policy $\pi$, $\mu_\pi(s) > 0, \forall s \in S$ -  the one from Puterman. Should I just clarify what I mean by "ergodicity" when I refer to it, given this ambiguity?  
  > **username_1**: Certainly makes sense to clarify which definition you use. The Moldovan definition concerns something other than ergodicity of MDPs, namely "beliefs over MDPs" in their language. For that I have no comments to add. Sutton (2) is a bit vague, and seems like they could mean something that either equals Puterman's ergodic OR unichain case. All this shows that ergodicity in a MDP is context dependent, could be a property of the MDP as a whole, or a policy, or something even different. Puterman is the authoritative source on MDP theory, and I find he gives very clear defintions of the fundamentals.  
  > **username_0**: I was unaware of the Puterman book. I'll certainly look into reading it. I have considered your answer as correct, as you provided a formal definition of ergodicity in an MDP. Given that I have always associated ergodicity with being able to eventually visit any state $s'$ from any other state $s$, I will probably be using Puterman's definition in the context of MDPs and Moldovan's in the context of policies. Thank you very much!  
  
  ---
  
  