Markov Decision Processes

A Markov decision process is a way to describe decision-making over time. The agent is in some current state, takes an action, the environment samples a next state, and the agent receives reward. The important modeling question is: what information must be in the state so that the next step can be predicted locally?

The Markov property says the current state and action contain everything needed to predict the next state distribution. If you are driving, your next position depends on where you are now and your steering choice. That is Markovian, assuming the current state includes the relevant driving facts.

Some processes are non-Markovian under an incomplete state description. Drawing marbles from a bag is a useful counterexample: if previous marbles have been removed and the current state omits what remains, the probability of the next draw depends on the draw history.

A Markov decision process, or MDP, packages a decision problem as:

$$M=\langle S,A,P,R,\gamma\rangle$$

$S$ is the set of states, $A$ is the set of actions, $P(s'\mid s,a)$ describes transition probabilities, $R(s,a,s')$ describes rewards, and $\gamma$ controls how much future reward counts.

The state representation is doing real work. A locked-door gridworld may be Markov if the state includes both position and whether the key has been collected. It may be non-Markov if the state only says "at the door," because the same visible state can lead to different next states depending on hidden history.