Markov Decision Process

Topics: Markov Chain - Stochastic Process

---

(definition)

A Markov decision process (MDP) is a Markov chain characterised by the ability to make a decision (among various options) in each state, incurring a cost for each decision taken in a given state.

MDPs can model diverse phenomena, making them useful when paired with optimisation. In this regard, several methods allow us to find the optimal policy for a given MDP.

Characterisation §

An MDP is characterised by the following 4 elements:

• $S=\{0,1,2,\dots ,m\}$, its state set
• $K=\{1,2,\dots ,k\}$, its set of decisions
• $C_{ik}$, the costs associated to taking the decision $k$ in the state $i$
• The transition matrices associated to a given decision $k$, whose elements are commonly denoted by $p_{ij}\{k\}$

Additionally, we may define $R=\left(r_1,r_2,\dots \right)$, the set of policies that can be formed with all the viable decisions in each state.