Content deleted Content added
→Algorithms: Added a reference on exact (rather than approximate) reduction to a finite model in some cases. |
m Open access bot: url-access=subscription updated in citation with #oabot. |
||
| (7 intermediate revisions by 7 users not shown) | |||
Line 3:
'''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 book |last1=Schneider |first1=S. |last2=Wagner |first2=D. H. |chapter=Error detection in redundant systems |date=1957-02-26 |title=Papers presented at the February 26-28, 1957, western joint computer conference: Techniques for reliability on - IRE-AIEE-ACM '57 (Western) |chapter-url=https://dl.acm.org/doi/10.1145/1455567.1455587 |___location=New York, NY, USA |publisher=Association for Computing Machinery |pages=115–121 |doi=10.1145/1455567.1455587 |isbn=978-1-4503-7861-1}}</ref><ref>{{Cite journal |last=Bellman |first=Richard |date=1958-09-01 |title=Dynamic programming and stochastic control processes |url=https://linkinghub.elsevier.com/retrieve/pii/S0019995858800030 |journal=Information and Control |volume=1 |issue=3 |pages=228–239 |doi=10.1016/S0019-9958(58)80003-0 |issn=0019-9958|url-access=subscription }}</ref> MDPs have since gained recognition in a variety of fields, including [[ecology]], [[economics]], [[Health care|healthcare]], [[telecommunications]] and [[reinforcement learning]].<ref name=":0">{{Cite book |last1=Sutton |first1=Richard S. |title=Reinforcement learning: an introduction |last2=Barto |first2=Andrew G. |date=2018 |publisher=The MIT Press |isbn=978-0-262-03924-6 |edition=2nd |series=Adaptive computation and machine learning series |___location=Cambridge, Massachusetts}}</ref> Reinforcement learning utilizes the MDP framework to model the interaction between a learning agent and its environment. In this framework, the interaction is characterized by states, actions, and rewards. The MDP framework is designed to provide a simplified representation of key elements of [[artificial intelligence]] challenges. These elements encompass the understanding of [[Causality|cause and effect]], the management of uncertainty and nondeterminism, and the pursuit of explicit goals.<ref name=":0" />
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.
Line 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 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.
Line 34:
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 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.
Line 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 109:
| 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|journal=Machine Learning|volume=49|issue=2/3 |pages=193–208 |doi=10.1023/A:1017932429737|doi-access=free}}</ref>
Line 182 ⟶ 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 266 ⟶ 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==
| |||