Markov decision process
1125883
226005910
2008-07-16T12:17:33Z
Rinconsoleao
4768911
Avoiding jargon
'''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 problem]]s solved via [[dynamic programming]] and [[reinforcement learning]]. MDPs were known at least as early as the 1950s (cf. Bellman 1957). Much research in the area was spawned due to [[Ronald A. Howard]]'s book, ''Dynamic Programming and Markov Processes'', 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]] [[Optimal_control_theory|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 <math>s</math> and an action <math>a</math>, a state transition function <math>P_a(s)</math> determines the transition probabilities to the next state. The decision maker earns a reward for each state transition. The state transitions of an MDP possess the ''[[Markov property]]'':given the state of the MDP at time <math>t</math> is known, transition probabilities to the state at time <math>t+1</math> are independent of all previous states or actions.
Markov decision processes are an extension of [[Markov chain]]s; 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 fixed for each state, a Markov decision process would reduce to a [[Markov chain]].
==Definition==
A Markov Decision Process is a list of four objects <math>(S,A,P_\cdot(\cdot,\cdot),R_a(\cdot,\cdot))</math>, where
* <math>S</math> is the state space,
* <math>A</math> is the action space,
* <math>P_a(s,s') = \Pr(s_{t+1}=s' \mid s_t = s,\, a_t=a)</math> is the probability that action <math>a</math> in state <math>s</math> at time <math>t</math> will lead to state <math>s'</math> at time <math>t+1</math>,
*<math>R_a(s,s')</math> is the immediate reward (or [[expected]] immediate reward) received after transition to state <math>s'</math> from state <math>s</math> with transition probability <math>P_a(s,s')</math>.
The goal is to maximize some cumulative function of the rewards, typically the discounted sum over a potentially infinite horizon:
*<math>\sum^{\infty}_{t=0}\gamma^t R_{a_t}(s_t, s_{t+1})</math>
where <math>\ \gamma \ </math> is the [[discount rate]] and satisfies <math>0 < \gamma \le 1</math>. It is typically close to 1.
==Solution==
The solution to a Markov Decision Process can be expressed as a ''policy'' <math>\pi</math>, a function from states to actions. 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'' <math>V</math>, which contains real values, and ''policy'' <math>\pi</math> which contains actions. At the end of the algorithm, <math>\pi</math> will contain the solution and <math>V(s_0)</math> will contain the discounted sum of the rewards to be earned (on average) by following that solution.
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.
:<math>\ \pi(s) := \arg \max_a \sum_{s'} P_a(s,s') V(s')\ </math>
:<math>\ V(s) := R(s) + \gamma \sum_{s'} P_{\pi(s)}(s,s') V(s')\ </math>
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), which is also called [[backward induction]],
the <math>\pi</math> array is not used; instead, the value of <math>\pi(s)</math> is calculated whenever it is needed.
Substituting the calculation of <math>\pi(s)</math> into the calculation of <math>V(s)</math> gives the combined step:
:<math>\ V(s) := R(s) + \gamma \max_a \sum_{s'} P_a(s,s') V(s')\ </math>
====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 <math>\pi</math> 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 <math>V</math> or <math>\pi</math> 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|partially observable Markov decision process}}
The solution above assumes that the state <math>s</math> is known when action is to be taken; otherwise <math>\pi(s)</math> cannot be calculated. When this assumption is not true, the problem is called a partially observable Markov decision process or POMDP.
===Learning===
If the probabilities are unknown, the problem is one of [[reinforcement learning]].
For this purpose it is useful to define a further function, which corresponds to taking the action <math>a</math> and then continuing optimally (or according to whatever policy one currently has):
:<math>\ Q(s,a) = R(s) + \gamma \sum_{s'} P_a(s,s') V(s')\ </math>
While this function is also unknown, experience during learning is based on <math>(s, a)</math> pairs (together with the outcome <math>s'</math>); that is, "I was in state <math>s</math> and I tried doing <math>a</math> and <math>s'</math> happened)". Thus, one has an array <math>Q</math> and uses experience to update it directly. This is known as [[Q-learning]].
===Minor extensions===
These extensions are minor in that they complicate the notation, but make no real difference to the problem or its solution.
* The reward may be a function of the action as well as the state, <math>R(s,a)</math>.
* The reward may be a function of the resulting state as well as the action and state, <math>R(s,a,s')</math>.
* The action space may be different at each state, so that it is <math>A_s</math> rather than <math>A</math>.
==Alternative notations==
The terminology and notation for MDPs are not entirely settled; there are two main streams — one using action, reward, value and <math>\gamma</math>, while the other uses control, cost, cost-to-go and <math>\alpha</math>. In addition, the notation for the transition probability varies.
{| border
! in this article !! alternative !! comment
|-
| action <math>a</math> || control <math>u</math> ||
|-
| reward <math>R</math> || cost <math>g</math>
| <math>g</math> is the negative of <math>R</math>
|-
| value <math>V</math> || cost-to-go <math>J</math>
| <math>J</math> is the negative of <math>V</math>
|-
| policy <math>\pi</math> || policy <math>\mu</math> ||
|-
| discounting factor <math>\ \gamma \ </math> || discounting factor <math>\alpha</math> ||
|-
| transition probability <math>P_a(s,s')</math> || transition probability <math>p_{ss'}(a)</math> ||
|}
In addition, transition probability is sometimes written <math>Pr(s,a,s')</math>, <math>Pr(s'|s,a)</math> or, rarely, <math>p_{s's}(a)</math>
==References==
* R. Bellman. ''A Markovian Decision Process''. Journal of Mathematics and Mechanics 6, 1957.
* R. E. Bellman. ''Dynamic Programming''. Princeton University Press, Princeton, NJ, 1957. Dover paperback edition (2003), ISBN 0486428095.
* 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.
* Sutton, R. S. and Barto A. G. ''Reinforcement Learning: An Introduction''. The MIT Press, Cambridge, MA, 1998.
* S. P. Meyn, 2007. [http://decision.csl.uiuc.edu/~meyn/pages/CTCN/CTCN.html Control Techniques for Complex Networks], Cambridge University Press, 2007. ISBN-13: 9780521884419. Appendix contains abridged [http://decision.csl.uiuc.edu/~meyn/pages/book.html Meyn & Tweedie].
==See also==
* [[Partially observable Markov decision process]]
* [[Dynamic programming]]
* [[Bellman equation]] for applications to economics.
==External links==
* [http://www.ai.mit.edu/~murphyk/Software/MDP/mdp.html MDP Toolbox for Matlab] - An excellent tutorial and Matlab toolbox for working with MDPs.
* [http://www.cs.ualberta.ca/~sutton/book/ebook Reinforcement Learning] An Introduction by Richard S. Sutton and Andrew G. Barto
* [http://www.computing.dundee.ac.uk/staff/jessehoey/spudd/index.html SPUDD] A structured MDP solver for download by Jesse Hoey
[[Category:Stochastic processes]]
[[Category:Optimization]]
[[Category:Dynamic programming]]
[[Category:Machine learning]]
[[fr:Processus de décision markovien]]
[[de:Markowkette]]