Markov Decision Processes

Markov property

Picture a chess board mid-game. To decide your best move you only need to look at the current position; it does not matter whether you reached it through a wild gambit or a quiet opening. The Markov property is exactly this idea: the present state holds everything you need to predict and decide, and the path that got you there adds nothing.

Stated precisely, a process is Markov if the distribution of the next state depends only on the current state and action, not on the earlier history. This is what lets an MDP store a small state instead of an ever-growing log, and it is the assumption that makes value functions and the Bellman equation work. When it fails, the fix is to fold enough history into the state until it holds again.

P(s_{t+1}\mid s_t,a_t)=P(s_{t+1}\mid s_t,a_t,s_{t-1},a_{t-1},\dots)

Given the present, the future is independent of the past.

Markov is a property of your state representation, not of the world; a richer state can restore it.

Also called
memorylessness