A Markov Decision Process (MDP) is a discrete time stochastic control process characterized by a set of states, actions, and transition probability matrices that depend on the actions chosen within a given state. It has the Markov property - the past is irrelevant for predicting the future, given knowledge of the present. December 2005 : January - February - March - April - May - June - July - August - September - October - November - December- → 31 December 2005 (Saturday) 25-year-old Scottish human rights worker Kate Burton and her parents are freed unharmed in the Gaza Strip by the Palestinian gunmen who kidnapped them two days earlier. ... Discrete time is non-continuous time. ... In mathematics, a (discrete-time) Markov chain is a discrete-time stochastic process with the Markov property. ... In probability theory, a stochastic process has the Markov property if the conditional probability distribution of future states of the process, given the present state, depends only upon the current state, i. ...

MDPs are useful for studying a wide range of optimization problems solved via dynamic programming and reinforcement learning. In computer science, an optimization problem is the problem to find among all feasible solutions for some problem the best one. ... In computer science, dynamic programming is a method for reducing the runtime of algorithms exhibiting the properties of overlapping subproblems and optimal substructure, described below. ... Reinforcement learning refers to a class of problems in machine learning which postulate an agent exploring an environment in which the agent perceives its current state and takes actions. ...

MDP is an essential component in reinforcement learning methods used in fabrication/fulfillment processes. Reinforcement learning refers to a class of problems in machine learning which postulate an agent exploring an environment in which the agent perceives its current state and takes actions. ...

MDPs are used in various areas, such as robotics, automated control and economics.

Definition

A Markov Decision Process is a tuple , where

• S is the State space,
• A is the action space,
• is the probability that action a in state s at time t will lead to state s' at time t + 1,
• R(x) is the immediate reward in state x.

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. In mathematics, a Markov chain is a discrete-time stochastic process with the Markov property named after Andrey Markov. ... In mathematics, a Markov chain is a discrete-time stochastic process with the Markov property named after Andrey Markov. ...

Solution

The solution to a Markov Decision Process can be expressed as a policy π, 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. In mathematics, a Markov chain is a discrete-time stochastic process with the Markov property named after Andrey Markov. ...

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 π, 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.

V(s): = R(s) + γ	∑	Pπ(s)(s,s')V(s')
	s'

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 π array is not used; instead, the value of π(s) is calculated whenever it is needed.

Substituting the calculation of π(s) into the calculation of V(s) gives the combined step:

V(s): = R(s) + γmaxa	∑	Pa(s,s')V(s')
	s'

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 π 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 π 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

Main article: partially observable Markov decision process

The solution above assumes that the state s is known when action is to be taken; otherwise π(s) cannot be calculated. When this assumption is not true, the problem is called a partially observable Markov decision process or POMDP. Overview The Partially Observable Markov Decision Process (POMDP) is an extension of the Markov Decision Process. ...

Learning

Main articles: reinforcement learning, Q-learning

It also assumes that the probabilities are known; if they are not, the problem is one of reinforcement learning. Reinforcement learning refers to a class of problems in machine learning which postulate an agent exploring an environment in which the agent perceives its current state and takes actions. ... Q-learning is a reinforcement learning technique that works by learning an action-value function that gives the expected utility of taking a given action in a given state. ... Reinforcement learning refers to a class of problems in machine learning which postulate an agent exploring an environment in which the agent perceives its current state and takes actions. ...

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) + γ	∑	Pa(s,s')V(s')
	s'

While this function is also not known, experience during learning is based on (s,a) pairs (together with the outcome s'), that is, "I was in state s and I tried doing a (and s' happened)". Thus, one has an array Q and uses experience to update it directly; known as Q-learning. Q-learning is a reinforcement learning technique that works by learning an action-value function that gives the expected utility of taking a given action in a given state. ...

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'), Pr(s' | s,a), p_ss'(a) or, rarely, p_s's(a)

• value: cost-to-go J (opposite sign to V)
• policy: μ
• discounting factor: α

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').
• 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

Overview The Partially Observable Markov Decision Process (POMDP) is an extension of the Markov Decision Process. ...

External links

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