Markov Decision Process

A Markov Decision Process is the process of looking at actions influencing state transitions. It is a sequential decision making problem for a fully observable yet stochastic environment.

Markov Chain holds, but now with probability of actions between states and rewards for action execution. This is reliant on two principles:

• Assume Markov property holds for action transitions.
• Probability distributions are stationary and don’t change.

We encode a reward for each state. Total utility of the agent is the sum of all rewards from all states visited.

A negative reward incentives optimality.

The MDP components for all states $s\in S$:

• transition model: $T(s,a,s^{\prime })$
• initial state of the problem: $s_0$
• reward function for a given state: $R(s)$

The MDP solution is not a plan of actions. The MDP solution is a policy $\pi$ which denotes the action $\pi (s)$ that should be taken for any state $s\in S$. The optimal policy (${\pi }^{\ast }$) will yield the highest expected utility in any given situation.