Answers.Body: <p>Your observation about the possibility of n being infinite makes sense. If an environment requires an infinite unbounded history of states to make decisions, it is considered non-Markovian. However, in the strict mathematical sense of (1st order Peano) arithmetic supposed to model all the natural numbers, any specific number n in its domain is finite, no matter how big it is. Thus your n-step Markovian is not non-Markovian as considered above.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-11T04:39:08.980Z
Answers.LastActivityDate: 2024-02-11T04:39:08.980Z
Answers.UserDisplayName: cinch
Body: <p>Several months ago, I was writing for class.  I claimed an environment was non-Markovian because it would take several states to de-alias some positions in the grid world.  I was corrected that it was n-step Markovian.  Something that didn't occur to me until the class had ended was:</p>
  <p>If there's an n, then n could be infinity.  This would imply an MDP where the next state is decidable with infinite history.  This seems like a reasonable thing to call non-Markovian as it's not decidable within a finite time but is it?  Where does non-Markovian start?</p>
  
Tags: <markov-decision-process>
Title: When is it non-Markovian?
UserDisplayName: foreverska
ThreadText: # When is it non-Markovian?
  
  (Asked by: username_0 on 2024-02-11)
  
  Several months ago, I was writing for class. I claimed an environment was non-Markovian because it would take several states to de-alias some positions in the grid world. I was corrected that it was n-step Markovian. Something that didn't occur to me until the class had ended was:
  
  If there's an n, then n could be infinity. This would imply an MDP where the next state is decidable with infinite history. This seems like a reasonable thing to call non-Markovian as it's not decidable within a finite time but is it? Where does non-Markovian start?
  
  **Tags:** markov-decision-process
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-02-11. Score: 1 | Accepted answer
  
  Your observation about the possibility of n being infinite makes sense. If an environment requires an infinite unbounded history of states to make decisions, it is considered non-Markovian. However, in the strict mathematical sense of (1st order Peano) arithmetic supposed to model all the natural numbers, any specific number n in its domain is finite, no matter how big it is. Thus your n-step Markovian is not non-Markovian as considered above.
  
  
  ---
  
  