Content deleted Content added
Arachnidly (talk | contribs) Technical corrections and better refs. will be back soon to fix more stuff and make it less scientific journal-y. |
m Open access bot: url-access=subscription updated in citation with #oabot. |
||
| (26 intermediate revisions by 17 users not shown) | |||
Line 1:
{{Short description|Mathematical model for sequential decision making under uncertainty}}
'''Markov decision process''' ('''MDP'''), also called a [[Stochastic dynamic programming|stochastic dynamic program]] or stochastic control problem, is a model for [[sequential decision making]] when [[Outcome (probability)|outcomes]] are uncertain.<ref>{{Cite book |last=Puterman |first=Martin L. |title=Markov decision processes: discrete stochastic dynamic programming |date=1994 |publisher=Wiley |isbn=978-0-471-61977-2 |series=Wiley series in probability and mathematical statistics. Applied probability and statistics section |___location=New York}}</ref>
Originating from [[operations research]] in the 1950s,<ref>{{Cite
The name comes from its connection to [[Markov chain|Markov chains]], a concept developed by the Russian mathematician [[Andrey Markov]]. The "Markov" in "Markov decision process" refers to the underlying structure of [[Transition system|state transitions]] that still follow the [[Markov property]]. The process is called a "decision process" because it involves making decisions that influence these state transitions, extending the concept of a Markov chain into the realm of decision-making under uncertainty.▼
▲The "Markov" in "Markov decision process" refers to the underlying structure of [[Transition system|state transitions]] that still follow the Markov property. The process is called a "decision process" because it involves making decisions that influence these state transitions, extending the concept of a Markov chain into the realm of decision-making under uncertainty.
==Definition==
Line 18 ⟶ 13:
* <math>S</math> is a [[set (mathematics)|set]] of states called the ''<dfn>state space</dfn>''. The state space may be discrete or continuous, like the [[set of real numbers]].
* <math>A</math> is a set of actions called the ''<dfn>action space</dfn>'' (alternatively, <math>A_s</math> is the set of actions available from state <math>s</math>). As for state, this set may be discrete or continuous.
* <math>P_a(s, s')</math> is, on an intuitive level, 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>. In general, this probability transition is defined to satisfy <math>\Pr(s_{t+1}\in S' \mid s_t = s, a_t=a)=\int_{S'} P_a(s, s')ds',</math> for every <math>S'\subseteq S</math> measurable. In case the state space is discrete, the integral is intended with respect to the [[counting measure]], so that the latter simplifies as <math>P_a(s, s')= \Pr(s_{t+1}=s' \mid s_t = s, a_t=a)</math>; In case <math>S\subseteq \mathbb R^d</math>, the integral is usually intended with respect to the [[Lebesgue measure]].
*<math>R_a(s, s')</math> is the immediate reward (or expected immediate reward) received after transitioning from state <math>s</math> to state <math>s'</math>, due to action <math>a</math>.
Line 31 ⟶ 26:
:<math>E\left[\sum^{\infty}_{t=0} {\gamma^t R_{a_t} (s_t, s_{t+1})}\right] </math> (where we choose <math>a_t = \pi(s_t)</math>, i.e. actions given by the policy). And the expectation is taken over <math>s_{t+1} \sim P_{a_t}(s_t,s_{t+1})</math>
where <math>\ \gamma \ </math> is the discount factor satisfying <math>0 \le\ \gamma\ \le\ 1</math>, which is usually close to <math>1</math> (for example, <math> \gamma = 1/(1+r) </math> for some discount rate <math>r</math>). A lower discount factor
Another possible, but strictly related, objective that is commonly used is the <math>H-</math>step return. This time, instead of using a discount factor <math>\ \gamma \ </math>, the agent is interested only in the first <math>H</math> steps of the process, with each reward having the same weight.
:<math>E\left[\sum^{H-1}_{t=0} {R_{a_t} (s_t, s_{t+1})}\right] </math> (where we choose <math>a_t = \pi(s_t)</math>, i.e. actions given by the policy). And the expectation is taken over <math>s_{t+1} \sim P_{a_t}(s_t,s_{t+1})</math>
where <math>\ H \ </math> is the time horizon. Compared to the previous objective, the latter one is more used in [[Learning Theory]].
A policy that maximizes the function above is called an ''<dfn>optimal policy</dfn>'' and is usually denoted <math>\pi^*</math>. A particular MDP may have multiple distinct optimal policies. Because of the [[Markov property]], it can be shown that the optimal policy is a function of the current state, as assumed above.
===Simulator models===
Line 39 ⟶ 40:
In many cases, it is difficult to represent the transition probability distributions, <math>P_a(s, s')</math>, explicitly. In such cases, a simulator can be used to model the MDP implicitly by providing samples from the transition distributions. One common form of implicit MDP model is an episodic environment simulator that can be started from an initial state and yields a subsequent state and reward every time it receives an action input. In this manner, trajectories of states, actions, and rewards, often called ''<dfn>episodes</dfn>'' may be produced.
Another form of simulator is a ''<dfn>generative model</dfn>'', a single step simulator that can generate samples of the next state and reward given any state and action.<ref name="Kearns Sparse">{{cite journal |last1=Kearns |first1=Michael |last2=Mansour |first2=Yishay |last3=Ng |first3=Andrew |title=A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes |journal=Machine Learning |date=2002 |volume=49 |issue=193–208 |pages=193–208 |doi=10.1023/A:1017932429737 |doi-access=free }}</ref> (Note that this is a different meaning from the term [[generative model]] in the context of [[statistical classification]].) In [[algorithms]] that are expressed using [[pseudocode]], <math>G</math> is often used to represent a generative model. For example, the expression <math>s', r \gets G(s, a)</math> might denote the action of sampling from the generative model where <math>s</math> and <math>a</math> are the current state and action, and <math>s'</math> and <math>r</math> are the new state and reward. Compared to an episodic simulator, a generative model has the advantage that it can yield data from any state, not only those encountered in a trajectory.
These model classes form a hierarchy of information content: an explicit model trivially yields a generative model through sampling from the distributions, and repeated application of a generative model yields an episodic simulator. In the opposite direction, it is only possible to learn approximate models through [[regression analysis|regression]]. The type of model available for a particular MDP plays a significant role in determining which solution algorithms are appropriate. For example, the [[dynamic programming]] algorithms described in the next section require an explicit model, and [[Monte Carlo tree search]] requires a generative model (or an episodic simulator that can be copied at any state), whereas most [[#Reinforcement learning|reinforcement learning]] algorithms require only an episodic simulator.
==Example==
[[File:Cartpole.gif|thumb|Pole Balancing example (rendering of the environment from the [[Open AI gym benchmark]])]]
An example of MDP is the Pole-Balancing model, which comes from classic control theory.
In this example, we have
* <math>S</math> is the set of ordered tuples <math>(\theta,\dot \theta, x, \dot x )\subset \mathbb R^4</math> given by pole angle, angular velocity, position of the cart and its speed.
* <math>A</math> is <math>\{-1,1\}</math>, corresponding to applying a force on the left (right) on the cart.
* <math>P_a(s, s')</math> is the transition of the system, which in this case is going to be deterministic and driven by the laws of mechanics.
*<math>R_a(s, s')</math> is <math>1</math> if the pole is up after the transition, zero otherwise. Therefore, this function only depend on <math>s'</math> in this specific case.
==Algorithms==
Solutions for MDPs with finite state and action spaces may be found through a variety of methods such as [[dynamic programming]]. The algorithms in this section apply to MDPs with finite state and action spaces and explicitly given transition probabilities and reward functions, but the basic concepts may be extended to handle other problem classes, for example using [[function approximation]]. Also, some processes with countably infinite state and action spaces can be <i>exactly</i> reduced to ones with finite state and action spaces.<ref name="Wrobel 1984">{{cite journal|first=A.|last=Wrobel|title=On Markovian decision models with a finite skeleton|journal=Zeitschrift für Operations Research|date=1984|volume=28|issue=1|pages=17–27|doi=10.1007/bf01919083|s2cid=2545336}}</ref>
The standard family of algorithms to calculate optimal policies for finite state and action MDPs 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)</math> will contain the discounted sum of the rewards to be earned (on average) by following that solution from state <math>s</math>.
Line 61 ⟶ 75:
====Value iteration====
In value iteration {{harv|Bellman|1957}}, which is also called [[backward induction]],
the <math>\pi</math> function is not used; instead, the value of <math>\pi(s)</math> is calculated within <math>V(s)</math> whenever it is needed. Substituting the calculation of <math>\pi(s)</math> into the calculation of <math>V(s)</math> gives the combined step;{{explain|reason=The derivation of the substituion is needed|date=July 2018}}
:<math> V_{i+1}(s) := \max_a \left\{ \sum_{s'} P_a(s,s') \left( R_a(s,s') + \gamma V_i(s') \right) \right\}, </math>
Line 92 ⟶ 106:
| volume=12
| issue=3
| pages=441–450 | doi=10.1287/moor.12.3.441
| access-date=November 2, 2023| hdl=1721.1/2893
| hdl-access=free
| url-access=subscription
}}</ref> However, due to the [[curse of dimensionality]], the size of the problem representation is often exponential in the number of state and action variables, limiting exact solution techniques to problems that have a compact representation. In practice, online planning techniques such as [[Monte Carlo tree search]] can find useful solutions in larger problems, and, in theory, it is possible to construct online planning algorithms that can find an arbitrarily near-optimal policy with no computational complexity dependence on the size of the state space.<ref>{{cite journal|last1=Kearns|first1=Michael|last2=Mansour|first2=Yishay|last3=Ng|first3=Andrew|date=November 2002|title=A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes
==Extensions and generalizations==
Line 135 ⟶ 150:
====Discrete space: Linear programming formulation====
If the state space and action space are finite, we could use linear programming to find the optimal policy, which was one of the earliest approaches applied. Here we only consider the ergodic model, which means our continuous-time MDP becomes an [[Ergodicity|ergodic]] continuous-time Markov chain under a stationary [[policy]]. Under this assumption, although the decision maker can make a decision at any time
:<math>g\geq R(i,a)+\sum_{j\in S}q(j\mid i,a)h(j) \quad \forall i \in S \text{ and } a \in A(i)</math>
If there exists a function <math>h</math>, then <math>\bar V^*</math> will be the smallest <math>g</math> satisfying the above equation. In order to find <math>\bar V^*</math>, we could use the following linear programming model:
Line 168 ⟶ 183:
our problem
:<math>\begin{align} V(s(0),0)= {} & \max_{a(t)=\pi(s(t))}\int_0^T r(s(t),a(t)) \, dt+D[s(T)] \\
\text{s.t.}\quad & \frac{
\end{align}
</math>
Line 179 ⟶ 194:
{{main|Reinforcement learning}}
[[Reinforcement learning]]
Reinforcement learning can solve Markov-Decision processes without explicit specification of the transition probabilities which are instead needed to perform policy iteration. In this setting, transition probabilities and rewards must be learned from experience, i.e. by letting an agent interact with the MDP for a given number of steps. Both on a theoretical and on a practical level, effort is put in maximizing the sample efficiency, i.e. minimimizing the number of samples needed to learn a policy whose performance is <math>\varepsilon-</math>close to the optimal one (due to the stochastic nature of the process, learning the optimal policy with a finite number of samples is, in general, impossible).
===Reinforcement Learning for discrete MDPs===
Line 186 ⟶ 203:
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]].
==Other scopes==
Line 193 ⟶ 208:
=== Learning automata ===
{{main|Learning automata}}
Another application of MDP process in [[machine learning]] theory is called learning automata. This is also one type of reinforcement learning if the environment is stochastic. The first detail '''learning automata''' paper is surveyed by [[Kumpati S. Narendra|Narendra]] and Thathachar (1974), which were originally described explicitly as [[finite
In learning automata theory, '''a stochastic automaton''' consists of:
Line 252 ⟶ 267:
==References==
{{Reflist}}
==Sources==
*{{citation|first=R.|last=Bellman|authorlink=Richard Bellman|year=1957|title=Dynamic Programming|publisher=Princeton University Press|isbn=978-0-486-42809-3}}. Dover paperback edition (2003)
==Further reading==
Line 264 ⟶ 282:
* {{cite book|last1=Sutton|first1=R. S.|last2=Barto|first2=A. G.|title=Reinforcement Learning: An Introduction|publisher=The MIT Press|___location=Cambridge, MA|year=2017|url=http://incompleteideas.net/sutton/book/the-book-2nd.html}}
* {{cite book|first=H.C.|last=Tijms.|title=A First Course in Stochastic Models|publisher=Wiley|year=2003|url=https://books.google.com/books?id=WibF8iVHaiMC|isbn=9780470864289}}
[[Category:Optimal decisions]]
| |||