Answers.Body: <p>The apparent issue here is that you are interpreting every visited state in a trajectory as part of the recurrent class which is incorrect. Only the limit behavior of the policy matters, which is described by the stationary distribution induced by the policy. Your MDP transition matrix is fine but the states that form the <em>recurrent class</em> are those that can be visited infinitely often under the stationary policy and satisfy the stationary state distribution.</p>
  <p>Finally you are correct that aperiodicity is restrictive, and aperiodicity is defined <em>per state</em> within the recurrent class of the transition matrix and ergodicity of the whole chain requires <em>all</em> states are <a href="https://en.wikipedia.org/wiki/Markov_chain#Ergodicity" rel="nofollow noreferrer">aperiodic with finite mean recurrence time</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-22T05:39:00.977Z
Answers.Text: Great thanks! Yeah I figured that only the limit behavior matters, but I don't think it's really mentioned in the sections I have read. I just checked and there is something about the limiting matix in Appendix A. Will have a look, thanks!
Answers.UserDisplayName: Simon
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-11-22T05:30:42.093Z
Answers.LastActivityDate: 2024-11-22T05:30:42.093Z
Answers.UserDisplayName: cinch
Body: <p>Puterman defines an ergodic MDP as</p>
  <blockquote>
  <p>if the transition matrix corresponding to every deterministic stationary policy consists of a single recurrent class.</p>
  </blockquote>
  <p>If the transition matrix is recurrent, it means that there is one aperiodic communicating class of states (the whole states space).</p>
  <p>However, this definition seems extremely restricting because of &quot;aperiodic&quot;.</p>
  <p>Consider a simple chainworld where every state is connected to every state. The whole state space is communicate. I could make a policy that always goes to one state (say X) and stays there forever. For example, the policy would induce the following trajectory: A, B, C, X, X, X, ...
  Clearly, I am visiting A, B, C once, but only X is recurrent.</p>
  <p>Am I interpreting the definition wrong? Should I consider only states visited in the limit? I.e., according to the stationary state distribution?</p>
  <p>Am I being correct assuming that the transition matrix is <span class="math-container">$P = \sum_a \mathcal{P}(s' | s, a) \pi(a|s)$</span> where <span class="math-container">$\mathcal{P}$</span> is the MDP dynamics matrix and <span class="math-container">$\pi$</span> is the policy?</p>
  <p>I found <a href="https://math.stackexchange.com/questions/152491/is-ergodic-markov-chain-both-irreducible-and-aperiodic-or-just-irreducible">this related question</a> but I didn't understand the answer.</p>
  <p><a href="https://ai.stackexchange.com/questions/27196/what-is-ergodicity-in-a-markov-decision-process-mdp">This question</a> is also related but does not seem to address my concern about &quot;aperiodic&quot;.</p>
  
Tags: <reinforcement-learning><markov-decision-process><ergodicity>
Title: Ergodic MDP: does it have to be aperiodic?
UserDisplayName: Simon
ThreadText: # Ergodic MDP: does it have to be aperiodic?
  
  (Asked by: username_0 on 2024-11-22)
  
  Puterman defines an ergodic MDP as
  
  > if the transition matrix corresponding to every deterministic stationary policy consists of a single recurrent class.
  
  If the transition matrix is recurrent, it means that there is one aperiodic communicating class of states (the whole states space).
  
  However, this definition seems extremely restricting because of "aperiodic".
  
  Consider a simple chainworld where every state is connected to every state. The whole state space is communicate. I could make a policy that always goes to one state (say X) and stays there forever. For example, the policy would induce the following trajectory: A, B, C, X, X, X, ...
  Clearly, I am visiting A, B, C once, but only X is recurrent.
  
  Am I interpreting the definition wrong? Should I consider only states visited in the limit? I.e., according to the stationary state distribution?
  
  Am I being correct assuming that the transition matrix is $P = \sum\_a \mathcal{P}(s' | s, a) \pi(a|s)$ where $\mathcal{P}$ is the MDP dynamics matrix and $\pi$ is the policy?
  
  I found [this related question](https://math.stackexchange.com/questions/152491/is-ergodic-markov-chain-both-irreducible-and-aperiodic-or-just-irreducible) but I didn't understand the answer.
  
  [This question](https://ai.stackexchange.com/questions/27196/what-is-ergodicity-in-a-markov-decision-process-mdp) is also related but does not seem to address my concern about "aperiodic".
  
  **Tags:** reinforcement-learning, markov-decision-process, ergodicity
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-11-22. Score: 2 | Accepted answer
  
  The apparent issue here is that you are interpreting every visited state in a trajectory as part of the recurrent class which is incorrect. Only the limit behavior of the policy matters, which is described by the stationary distribution induced by the policy. Your MDP transition matrix is fine but the states that form the *recurrent class* are those that can be visited infinitely often under the stationary policy and satisfy the stationary state distribution.
  
  Finally you are correct that aperiodicity is restrictive, and aperiodicity is defined *per state* within the recurrent class of the transition matrix and ergodicity of the whole chain requires *all* states are [aperiodic with finite mean recurrence time](https://en.wikipedia.org/wiki/Markov_chain#Ergodicity).
  
  > **Comments:**
  > **username_0**: Great thanks! Yeah I figured that only the limit behavior matters, but I don't think it's really mentioned in the sections I have read. I just checked and there is something about the limiting matix in Appendix A. Will have a look, thanks!  
  
  ---
  
  