<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>

CC BY-SA 4.0
2024-02-11T04:39:08.980Z
2024-02-11T04:39:08.980Z
cinch
<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>

<markov-decision-process>
When is it non-Markovian?
foreverska
# 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.


---

