Markov decision processes (MDPs) provide a mathematical framework for modeling decision-making in situations where outcomes are partly random and partly under the control of the decision maker. MDPs are useful for studying a wide range of optimization problems solved via dynamic programming and reinforcement learning. They were invented by Ronald Howard in 1960. Today they are used in a variety of areas, including robotics, automated control, economics and in manufacturing.

More precisely a Markov Decision Process is a discrete time stochastic control process characterized by a set of states; in each state there are several actions from which the decision maker must choose. For a state s and an action a, a state transition function $P\_a(s)$ determines the transition probabilities to the next state. After the next state is entered the decision maker earns a reward which depends on the new state. The states of an MDP possesses the Markov property. This means that if the current state of the MDP at time $t$ is known, transitions to a new state at time $t+1$ are independent of all previous states.

Definition

---

A Markov Decision Process is a tuple $(S,A,P\_\backslash cdot(\backslash cdot,\backslash cdot),R(\backslash cdot))$, where

• $S$ is the State space,
• $A$ is the action space,
• $P\_a(s,s\text{'})\; =\; \backslash Pr(s\_\{t+1\}=s\text{'}\; |\; s\_t\; =\; s,\backslash ,\; a\_t=a)$ is the probability that action $a$ in state $s$ at time $t$ will lead to state $s\text{'}$ at time $t+1$,
• $R(s,a)$ is the expected reward for taking an action $a$ in state $s$.

The goal is to maximize some cumulative function of the rewards, typically the discounted sum under a discounting factor γ (usually just under 1).

Markov decision processes are an extension of Markov chains; the difference is the addition of actions (allowing choice) and rewards (giving motivation). If there were only one action, or if the action to take were somehow fixed for each state, a Markov decision process would reduce to a Markov chain.

Solution

---

The solution to a Markov Decision Process can be expressed as a policy $\backslash pi$, which gives the action to take for a given state, regardless of prior history. Note that once a Markov decision process is combined with a policy in this way, this fixes the action for each state and the resulting combination behaves like a Markov chain.

The standard family of algorithms to calculate the policy requires storage for two arrays indexed by state: value $V$, which contains real values, and policy $\backslash pi$, which contains actions and will contain the solution at the end of the algorithm.

The algorithm then has the following two kinds of steps, which are repeated in some order for all the states until no further changes take place.

$\backslash pi(s)\; :=\; \backslash arg\; \backslash max\_a\; \backslash sum\_\{s\text{'}\}\; P\_a(s,s\text{'})\; V(s\text{'})$

$V(s)\; :=\; R(s)\; +\; \backslash gamma\; \backslash sum\_\{s\text{'}\}\; P\_\{\backslash pi(s)\}(s,s\text{'})\; V(s\text{'})$

Their order depends on the variant of the algorithm; one can also do them for all states at once or state by state, and more often to some states than others. As long as no state is permanently excluded from either of the steps, the algorithm will eventually arrive at the correct solution.

Notable variants

Value iteration

In value iteration (Bellman 1957), the $\backslash pi$ array is not used; instead, the value of $\backslash pi(s)$ is calculated whenever it is needed.

Substituting the calculation of $\backslash pi(s)$ into the calculation of $V(s)$ gives the combined step:

$V(s)\; :=\; R(s)\; +\; \backslash gamma\; \backslash max\_a\; \backslash sum\_\{s\text{'}\}\; P\_a(s,s\text{'})\; V(s\text{'})$

Policy iteration

In policy iteration (Howard 1960), step one is performed once, and then step two is repeated until it converges. Then step one is again performed once and so on.

Instead of repeating step two to convergence, it may be formulated and solved as a set of linear equations.

This variant has the advantage that there is a definite stopping condition: when the array $\backslash pi$ does not change in the course of applying step 1 to all states, the algorithm is completed.

Modified policy iteration

In modified policy iteration (Puterman and Shin 1978), step one is performed once, and then step two is repeated several times. Then step one is again performed once and so on.

Prioritized sweeping

In this variant, the steps are preferentially applied to states which are in some way important - whether based on the algorithm (there were large changes in $V$ or $\backslash pi$ around those states recently) or based on use (those states are near the starting state, or otherwise of interest to the person or program using the algorithm).

Extensions

---

Partial observability

The solution above assumes that the state $s$ is known when action is to be taken; otherwise $\backslash pi(s)$ cannot be calculated. When this assumption is not true, the problem is called a partially observable Markov decision process or POMDP.

Learning

It also assumes that the probabilities are known; if they are not, the problem is one of reinforcement learning.

For this purpose, it's useful to define a further function, which corresponds to taking the action $a$ and then continuing optimally (or according to whatever policy one currently has):

$Q(s,a)\; =\; R(s)\; +\; \backslash gamma\; \backslash sum\_\{s\text{'}\}\; P\_a(s,s\text{'})\; V(s\text{'})$

While this function is also not known, experience during learning is based on $(s,\; a)$ pairs (together with the outcome $s\text{'}$), that is, "I was in state $s$ and I tried doing $a$ (and $s\text{'}$ happened)". Thus, one has an array $Q$ and uses experience to update it directly; known as Q-learning.

Alternative notations

---

Various minor variants exist, either just using different variable names, or representing minor extensions. These

Variable names

Alternative variable names:

• action: control $u$.
• reward: cost $g$ (opposite sign to $R$)
• transition probability: $Pr(s,a,s\text{'})$, $Pr(s\text{'}|s,a)$, $p\_\{ss\text{'}\}(a)$ or, rarely, $p\_\{s\text{'}s\}(a)$

• value: cost-to-go $J$ (opposite sign to $V$)
• policy: $\backslash mu$
• discounting factor: $\backslash alpha$

Minor extensions

• The reward may be a function of the action as well as the state, $R(s,a)$.
• The reward may be a function of the resulting state as well as the action and state, $R(s,a,s\text{'})$.
• The action space may be different at each state, so that it is $A\_s$ rather than $A$

References

---

• Bellman, R. E. Dynamic Programming. Princeton University Press, Princeton, NJ.
• Ronald A. Howard Dynamic Programming and Markov Processes, The M.I.T. Press, 1960.
• M. L. Puterman. Markov Decision Processes. Wiley, 1994.
• H.C. Tijms. A First Course in Stochastic Models. Wiley, 2003.
• Sutton, R.S. " On the significance of Markov decision processes" . In W. Gerstner, A. Germond, M. Hasler, and J.-D. Nicoud (Eds.) Artificial Neural Networks -- ICANN'97, pp. 273-282. Springer.

See also

---

• Partially observable Markov decision process

External links

---

• MDP Toolbox for Matlab - An excellent tutorial and Matlab toolbox for working with MDPs.

Stochastic processes | Machine learning