Markov Decision Processes

Definition

Example of a simple MDP with three states (green circles) and two actions (orange circles), with two rewards (orange arrows)

Markov decision process (MDP) is a tuple $(S,A,P,R)$. Where:

• $S$: A set of states (State space)
• $A$: A set of actions (Action space)
• $P_{s{s}^{\prime }}^a=p(s^{\prime }|s,a)=P(S_{t+1}=s^{\prime }|S_t=s,A_t=a)$: A Transition Probability from $s$ to $s^{\prime }$ given $a$.
• $R_{s{s}^{\prime }}^a=r(s,a,s^{\prime })$: The immediate Reward received after transitioning from state $s$ to $s^{\prime }$ due to action $a$.

Facts

Environmental model in MDP is the Transition Probability. If the Transition Probability is known, it is called a model-based MDP, otherwise called a model-free MDP.

Any Markov decision process satisfies the followings:

• There exists an optimal policy $\exists {\pi }_{\ast }\text{s.t.}\forall \pi ,\forall s,v_{{\pi }_{\ast }}(s)\ge v_{\pi }(s)$
• All optimal policies achieve the optimal state-value function $v_{{\pi }_{\ast }}(s)=v_{\ast }(s)$
• All optimal policies achieve the optimal action-value function $q_{{\pi }_{\ast }}(s,a)=q_{\ast }(s,a)$