Editing Markov decision process (section)

==Extensions and generalizations==
A Markov decision process is a [[stochastic game]] with only one player.

===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.

=== Constrained Markov decision processes ===
Constrained Markov decision processes (CMDPS) are extensions to Markov decision process (MDPs). There are three fundamental differences between MDPs and CMDPs.<ref>{{cite book|last=Altman|first=Eitan|title=Constrained Markov decision processes|volume=7|publisher=CRC Press|year=1999}}</ref>

* There are multiple costs incurred after applying an action instead of one.
* CMDPs are solved with [[Linear programming|linear programs]] only, and [[dynamic programming]] does not work.
* The final policy depends on the starting state.

The method of Lagrange multipliers applies to CMDPs.
Many Lagrangian-based algorithms have been developed.
* Natural policy gradient primal-dual method.<ref>
{{cite conference
 | last1 = Ding | first1 =Dongsheng
 | last2 = Zhang | first2 = Kaiqing
 | last3 = Jovanovic | first3 = Mihailo
 | last4 = Basar | first4 = Tamer
 | year = 2020
 | title = Natural policy gradient primal-dual method for constrained Markov decision processes
 | conference = Advances in Neural Information Processing Systems
}}
</ref>

There are a number of applications for CMDPs. It has recently been used in [[motion planning]] scenarios in robotics.<ref>{{cite conference |last1=Feyzabadi |first1=S. |last2=Carpin |first2=S. |title=Risk-aware path planning using hierarchical constrained Markov Decision Processes |book-title=Automation Science and Engineering (CASE) |conference=IEEE International Conference |pages=297, 303 |date=18–22 Aug 2014 |url=https://www.researchgate.net/publication/270105954}}</ref>

===Continuous-time Markov decision process===
In discrete-time Markov Decision Processes, decisions are made at discrete time intervals. However, for '''continuous-time Markov decision processes''', decisions can be made at any time the decision maker chooses. In comparison to discrete-time Markov decision processes, continuous-time Markov decision processes can better model the decision-making process for a system that has [[Continuous time|continuous dynamics]], i.e.,&nbsp;the system dynamics is defined by [[ordinary differential equation]]s (ODEs). These kind of applications raise in [[queueing system]]s, epidemic processes, and [[population process]]es.

Like the discrete-time Markov decision processes, in continuous-time Markov decision processes the agent aims at finding the optimal ''policy'' which could maximize the expected cumulated reward. The only difference with the standard case stays in the fact that, due to the continuous nature of the time variable, the sum is replaced by an integral:
:<math>\max \operatorname{E}_\pi\left[\left. \int_0^\infty\gamma^t r(s(t),\pi(s(t))) \, dt \;\right| s_0 \right]</math>
where <math>0\leq\gamma< 1.</math>

====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 in the current state, there is no benefit in taking multiple actions. It is better to take an action only at the time when system is transitioning from the current state to another state. Under some conditions,<ref>{{Cite book |url=https://link.springer.com/book/10.1007/978-3-642-02547-1 |title=Continuous-Time Markov Decision Processes |series=Stochastic Modelling and Applied Probability |date=2009 |volume=62 |language=en |doi=10.1007/978-3-642-02547-1|isbn=978-3-642-02546-4 }}</ref> if our optimal value function <math>V^*</math> is independent of state <math>i</math>, we will have the following inequality:
:<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:
*Primal linear program(P-LP)
:<math>
\begin{align}
\text{Minimize}\quad &g\\
\text{s.t} \quad & g-\sum_{j \in S}q(j\mid i,a)h(j)\geq R(i,a)\,\,
\forall i\in S,\,a\in A(i)
\end{align}
</math>
*Dual linear program(D-LP)
:<math>
\begin{align}
\text{Maximize} &\sum_{i\in S}\sum_{a\in A(i)}R(i,a)y(i,a)\\
\text{s.t.} &\sum_{i\in S}\sum_{a\in A(i)} q(j\mid i,a)y(i,a)=0 \quad
\forall j\in S,\\
& \sum_{i\in S}\sum_{a\in A(i)}y(i,a)=1,\\
& y(i,a)\geq 0 \qquad \forall a\in A(i) \text{ and } \forall i\in S
\end{align}
</math>
<math>y(i,a)</math> is a feasible solution to the D-LP if <math>y(i,a)</math> is nonnative and satisfied the constraints in the D-LP problem. A feasible solution <math>y^*(i,a)</math> to the D-LP is said to be an optimal solution if
:<math>
\begin{align}
\sum_{i\in S}\sum_{a\in A(i)}R(i,a)y^*(i,a) \geq  \sum_{i\in S} \sum_{a\in A(i)} R(i,a) y(i,a)
\end{align}
</math>
for all feasible solution <math>y(i,a)</math> to the D-LP. Once we have found the optimal solution <math>y^*(i,a)</math>, we can use it to establish the optimal policies.

====Continuous space: Hamilton–Jacobi–Bellman equation====
In continuous-time MDP, if the state space and action space are continuous, the optimal criterion could be found by solving [[Hamilton–Jacobi–Bellman equation|Hamilton–Jacobi–Bellman (HJB) partial differential equation]]. In order to discuss the HJB equation, we need to reformulate
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{d s(t)}{dt}=f[t,s(t),a(t)]
\end{align}
</math>

<math>D(\cdot)</math> is the terminal reward function, <math>s(t)</math> is the system state vector, <math>a(t)</math> is the system control vector we try to find. <math>f(\cdot)</math> shows how the state vector changes over time. The Hamilton–Jacobi–Bellman equation is as follows:
:<math>0=\max_u ( r(t,s,a) +\frac{\partial V(t,s)}{\partial x}f(t,s,a)) </math>
We could solve the equation to find the optimal control <math>a(t)</math>, which could give us the optimal [[value function]] <math>V^*</math>